CODEWITHSUNDEEP
pythonwhile-loop
Ari
Ari

Reputation: 6169

My simple while loop hangs my computer on larger inputs

This is my response to a HackerRank challenge

https://www.hackerrank.com/challenges/repeated-string

def repeatedString(s, n):
   string = ''
   count = 0

   while len(string) < n:
      for letter in s:
         if len(string) != n:
            string += letter
            if letter == 'a':
               count += 1
   return count

print(repeatedString('aba', 10))
>> 7 # works!

's' is a string input eg. 'abc', which theoretically repeats forever. 'n' is the number of characters I need to use of that infinite string, eg. 'abcabcabca' if n = 10

I then need to find the number of occurrences of 'a', my function works fine on small integers but for the test case in the question, they use 1000000000000 and everything times-out, even on my laptop.

Is there a more efficient and less resource intensive way of doing this?

Upvotes: 0

Views: 62

Answers (1)

iz_
iz_

Reputation: 16593

You can just do some math instead of looping:

def repeatedString(s, n):
   q, r = divmod(n, len(s))
   return s.count('a') * q + s[:r].count('a')

The value of n doesn't matter for this solution. repeatedString('abca', 100000000000000000000000) runs only 30% slower than repeatedString('abca', 10).

Upvotes: 4

Related Questions