My simple while loop hangs my computer on larger inputs

26
January 26, 2019, at 1:40 PM

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?

Answer 1

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).

READ ALSO
How to get the class of Map type

How to get the class of Map type

I have to pass the class type of Map<String, CountryConfig> in the line new CouchbaseDAO<>(cbClientProvider, new CountryConfigKeyProvider(), class); in place of class that is in third argumentBut it is not taking it , i have tried like Map

41
How to add paypals buyer protection banner under every product image on woocomerce?

How to add paypals buyer protection banner under every product image on woocomerce?

I want to add paypals buyer protection banner under every product image on woocommerce single product pageI have followed paypal given document and added their script in single-product

50