So there's one more problem I cannot think any way of solving except brute force.

Question:

There's a array of strings, each string represents a number(length of string can be 10^5)

For each number represented as a string, we want to find whether it's of the form x^3 or x^3+4

(It's certain that number will be in either form)

The number are very large if the length of the string is 10^5 so we cannot use brute force or anything, any ideas?

Thank you

My friend had a coding test today and he had this question that he wasn't able to solve, like wise for me after thinking I could only see the brute force approach.

The Question.

There's an initial string given str which has only A,B,C now a sequence of strings is created S where S[0]=str and then S[i] is made from S[i-1] after replacing A by BC and B by CA and C by AB for ex. if s[0]=AB then S[1]= BCCA ( A was replaced by BC and B by CA)

Now there's m queries given, in each query there's two integers i and j and we want to print the i th character of S[j]

. Ex str=A m=1 i=1 j=2

S[1]=BC S[2]=CAAB

and 1st character of S[2] is C.

i and j goes to 10^9 m goes to 10^5

I could only think of the brute force approach which obviously wouldn't work, could you share a better approach?