# 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

« Back to problem overview