Hackerrank Solution: Repeated String

Original Problem

Lilah has a string, \(s\), of lowercase English letters that she repeated infinitely many times.

Given an integer, \(n\), find and print the number of letter a's in the first \(n\) letters of Lilah's infinite string.

For example, if the string \(s='abcac'\) and \(n=10\) , the substring we consider is \(abcacabcac\), the first \(10\) characters of her infinite string. There are \(4\) occurrences of a in the substring.

Function Description

Complete the repeatedString function in the editor below. It should return an integer representing the number of occurrences of a in the prefix of length \(n\) in the infinitely repeating string.

repeatedString has the following parameter(s):

• s: a string to repeat
• n: the number of characters to consider

Input Format

The first line contains a single string, \(s\). The second line contains an integer, \(n\).

Constraints

• \(1\leq|s|\leq 100\)
• \(1\leq n \leq 10^{12}\)

Output Format

Print a single integer denoting the number of letter a's in the first \(n\) letters of the infinite string created by repeating infinitely many times.

Solution

When concatenating the given string \(s\) indefinitely and requiring to test how many a's within the interval \([0, n)\) are present, the string fits exactly \(\left\lfloor \frac{n}{|s|}\right\rfloor\) times into the interval. Knowing how many a's are present in \(s\) allows us to scale it accordingly. However, if \(|s|\) does not divide \(n\) evenly, there is a chance a substring of length \(n\bmod |s|\) is left, so we have to count the a's in this remaining substring as well. Implementing this \(O(|s|)\) idea in Python leads to

def repeatedString(s, n):
    r = 0
    l = len(s)
    for i in range(0, l):
        if s[i] == 'a':
            r+= 1
    r*= int(n / l)
    for i in range(0, n % l):
        if s[i] == 'a':
            r+= 1
    return r