Algorithm to find a number and its square in an array -


I have an array of integers, and I need an O algorithm to know that array Has a number and its square; A pair is enough.

I tried to do it myself, but I only managed to find a solution in O (n 2 ).

I thought of using counting sort, but memory usage is too big.

Create an array twice the heap of the input array (2n)
o (n) Copy all the numbers in - O (N)
Copy sections of numbers in radix sort (we can do this because they are all intents) o (n)
to see it once again After the other O (N) profits two numbers are the same! O (1)


Comments

Post a Comment