How to solve the problem Square or Cube from Airtel Crack the Code ?

@meooow What hash function did u use?

can you please share your code ?

Here it is: https://ideone.com/wv8Dj1

I am sure it’s a bit difficult to understand it.

@vivek_1998299 a polynomial hash like you mentioned: hash_2(n) = \sum_p (cnt_n(p) \bmod 2) \cdot base ^ p \mod M where p is prime and cnt_n(p) is the number of times p divides n. It is similar for hash_3. If you want the code: link.

@meooow Yeah you’re right, 6 is enough. I was thinking of taking a prime close to the length of the string as ‘Mod’, and use binary exponentiation for updating. I saw a different hash function here : https://threads-iiith.quora.com/String-Hashing-for-competitive-programming . But we can precompute powers instead.

@hemant i tried using the hash function u mentioned in one of my past hackerrank question,however couldnt get AC(got 50/55) due to collisions.Plz tell if u could find a perfect value of p,mod

(Particularly for strings with 26 characters)

@hemanth_1 actually the hash I used is the same as the one described in that article. Here you can consider the character S_i is cnt_n(i) \bmod 2 when i is prime and 0 when it is not. The difference from the string case is that, as you said when describing the approach, here from hash(x) to hash(xy) some characters change instead of only a new character being added.

Lets maintain a prefix product array to get the product between l and r,then we can precompute all cubes and squares less than 10^11 and binarySearch on it to get the result.