Loop while not working well - Hakerrank

Question

I’m trying to solve the Hackerrank repeated string problem, where we should build a function that counts the number of letters a repeat in a string bounded by an n number. The function entries are n (limiter number) and s, which is the base string. Let’s assume that s = 'abc'. If n = 10, then I must count the number of letters a in the string 'abcabcabca'. I did the following function and can not understand why the while is not working:

def repeatedString(s, n):
    lista = list(s)
    listaextra = []
    a = 0
    i = 3
    while i in (len(s), n-len(s)):
        listaextra.append(lista[i%len(s)])
        i += 1
        
    listafinal = lista + listaextra
    for x in range(len(listafinal)):
        if listafinal[x] == 'a':
            a+=1
    return a, i, lista, listaextra, len(s), n-len(s)

She at the end gives me this return: (3, 4, ['a', 'b', 'a'], ['a'], 3, 7) For this input: n = 10, s = 'tab'

Can anyone tell me the problem with this code?

Answer 1

Can anyone tell me the problem with this code?

Yes, I say the code is all wrong. For the following reasons:

• The approach is too complicated for a simple problem.
• It doesn’t even solve your initial problem of building a string based on another to count the characters a repeated.
• Is difficult to interpret.
• Even if the code was fixed the algorithm would have performance.

If you have a string s and wants to repeat it until n the best approach is to divide the length of s for n to know how many times s shall be repeated and with the rest of the division take a fraction of s which will complete the missing characters. Python offers the built-in function divmode() that in an operation returns the quotient and the rest of a division:

>>>s = 'abc'
>>>n = 10
>>>dm = divmod(n, len(s))
>>>print(s * dm[0] + s[:dm[1]])
abcabcabca

^{Test the code on Ideone}

Where:

• s * dm[0] is the string s repeated by the quotient dm[0].
• s[:dm[1]] is the fraction of the string s determined by the rest dm[1].

So, or you can count how many times the character a is repeated in the resulting string with the help of the method str.count():

>>>s = 'abc'
>>>n = 10
>>>dm = divmod(n, len(s))
>>>res = s * dm[0] + s[:dm[1]]
>>>print(res.count("a"))
4

^{Test the code on Ideone}
This solution has the disadvantage of memory consumption in the case of n be very big, example n = 1000000000, with multilinear time complexity O(Len(s)*n).

If you want performance, instead of counting how many times the character a repeats in the resulting string you can count once how many times the letter a appears in the string s multiply by the quotient and count again how many times the letter a fraction of the string appears s:

>>>s = 'abc'
>>>n = 10
>>>dm = divmod(n, len(s))
>>>c1 = s.count("a") * dm[0]
>>>c2 = s[:dm[1]].count("a")
>>>print(c1 + c2)
4

^{Test the code on Ideone}
This solution already has constant time complexity O(1) and works well with absurd values to n and s.

Packaging the solution as a function:

def repeatedString(s, n):
  dm = divmod(n, len(s))
  c1 = s.count("a") * dm[0]
  c2 = s[:dm[1]].count("a")
  return c1 + c2

print(repeatedString('abc',11234567890987654321))  #3744855963662551441

^{Test the code on Ideone}

Answer 2

Hello...

• First his return is returning a tupla with all the values you asked to be returned, this happens because: python does not allow multiple returns, so it throws all of this inside a tupla and returns it. Hence this giant function return repeatedString.

• According to your code there are some logic errors and it is much more complex than it needs to be. For example: the value being counted in the variable a It is not right, the creation of 3 different lists is unnecessary in my opinion, I solved the exercise with 2 lists. But with a greater amount of looping loops.

• I would also like to say that I did not understand exactly your while i in (len(s), n-len(s)). I got a little confused on this part. So I guess I can’t explain why your bow tie while does not work. However, below is my resolution of the exercise. Any doubt is just talk!

def repeatedString(s, n):
    #len de lista tem que ser igual a N
    base = ['0'] * n #lista com tamanho que a lista final devera ficar
    lista_final = []
    cont = 0 #contador
    a = 0 #quantida de 'a'
    while cont < len(base):
        for valores in s: #quebra a string em 's' e caracteres. Ex: "a", "b", "c"
            cont += 1 #soma 1 em cont
            if cont > len(base): #se cont for maior que o tamanho da lista base ignora e deixa o programa voltar ao while que dara False
                pass
            else:
                lista_final.append(valores) #adiciona valores em lista_final
    for x in range(len(lista_final)):
        if lista_final[x] == 'a': #verifica se em lista_final na posicao x existe a letra a
            a += 1 #se o if for True adiciona +1 na variavel a
    
    return a #retorna o valor da variavel a

string = input()
numero = int(input()) 
funcao = repeatedString(string, numero)
print(funcao) #printa o retorno da funcao repeatedString