找出所有由300个数字排列组成的完全平方数。

Question

这是我朋友在谷歌面试时被问到的一个问题。他当时无法想出解决方案，但最终还是得到了这份工作。以下是问题：

你得到了300个数字，其中包括100个1，100个2和100个3，请设计一种算法来确定所有完全平方数。

我也尝试了一段时间，但卡住了。对于该如何解决此问题是否有任何想法？

- sanz

---

每个答案必须使用所有提供的数字，还是可以使用任意子集？ - cheeken

我认为这意味着所有数字都有300位数。 - Mitch Wheat

@cheeken 每个答案都需要使用所有的300个数字。 - sanz

哇。如果我们假装这不是一个骗局问题，即使只是检查一个300位数字是否为平方数，也是一个巨大的问题（参见SO讨论）。除此之外，你可能还需要测试大量的排列组合。 - AlexQueue

@Queequeg：这是有诈骗的第一个线索。 - jason

Answer 1

   printf ("{}\n"); 

所讨论的集合为空集（数字的各位数之和可被3整除但不可被9整除）。

- n. m.

---

对于不理解的人：如果数字的各个位数之和可以被3整除，那么这个数字就可以被3整除。同样的规则适用于9。由于这个数字的各个位数之和可以被3整除但不能被9整除，所以这个数字是3的倍数但不是9的倍数。一个完全平方数不能恰好有一个3的因数。 - Mysticial

Answer 2

n.m 的答案当然很好。

很容易看出，唯一一个可以使其平方的最后一位为{1,2,3}之一的数字是以9为个位数字的数。现在，如果我们使用9作为数字的最后一位，使其平方为这些组合中的一个，我们很快就会发现，在十位数字和9的个位数字中没有10的数字可以在它的平方的十位数字中涉及到{1,2,3}。

可能，这个解释回答了一个问题，例如“300个数字的任何组合是否都有平方根为1,2和3”？

- grdvnl