25

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 comprising 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?

phuclv
  • 37,963
  • 15
  • 156
  • 475
sanz
  • 1,069
  • 1
  • 10
  • 26
  • 1
    Must each answer use all of the provided digits, or any subset? – cheeken Sep 18 '11 at 05:45
  • 1
    I would think it implied that the numbers all have 300 digits. – Mitch Wheat Sep 18 '11 at 06:02
  • @cheeken all the 300 digits need to be used for each answer. – sanz Sep 18 '11 at 17:15
  • Wow. If we pretend that this isn't a trick question, even just checking whether or not a 300 digit number is a square is a huge problem on its own [(SO discussion)](http://stackoverflow.com/questions/295579/fastest-way-to-determine-if-an-integers-square-root-is-an-integer). On top of that, you would probably need to test an absurd number of permutations. – AlexQueue Sep 20 '11 at 15:16
  • @Queequeg: Which is the first clue that there is a trick. – jason Sep 23 '11 at 04:17

2 Answers2

56
   printf ("{}\n");

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

n. m. could be an AI
  • 112,515
  • 14
  • 128
  • 243
  • 21
    To anyone who doesn't understand why: If the sum of the digits is divisible by 3, the number is divisible by 3. Same applies to 9. Since the sum of the digits is divisible by 3 but not 9, the number is a multiple of 3 but not 9. A perfect square can't have exactly one factor of 3. – Mysticial Sep 18 '11 at 05:49
0

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"?

grdvnl
  • 636
  • 6
  • 9