Find all perfect squares that are a permutation of some 300 digits

This was a question that was asked to my friend in a Google interview a while back. He was unable to come up with a solution but ended up bagging the job anyway. Here's the question

You have been given 300 digits comprisi开发者_如何学运维ng of 100 ones, 100 twos, and 100 threes, now come up with an algorithm that will determine all such numbers which are a perfect square

I tried this for a while but am stumped. Any thoughts on how to go about this?

   printf ("{}\n"); 

The set in question is empty (the sum of the digits is divisible by 3 but not by 9).

n.m's answer is of course great.

It is also easy to see that the only number that can have its square have last digit among {1,2,3} is a number starting with unit digit as 9. Now, if we use 9 as the last digit of a number that would square to one of the combinations, we will soon see that there is no 10's digit along with 9 at unit digit that can give a number involving {1,2,3} in the 10th digit of its square.

Probably, this explanation answers a question like "does any combination of 300 digits with 1,2 and 3 have a square root"?