找出 300 个数字的排列的所有完全平方数
这是不久前在 Google 面试中向我的朋友提出的问题。他无法想出解决方案，但最终还是得到了这份工作。这是问题
您已获得 300 个数字，其中包括 100 个一、100 个二和 100 个三，现在想出一个算法来确定所有这些数字是否是完全平方数
我尝试了一段时间但被难住了。关于如何解决这个问题有什么想法吗？
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?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
所讨论的集合是空的（数字之和可以被 3 整除，但不能被 9 整除）。
The set in question is empty (the sum of the digits is divisible by 3 but not by 9).
nm的回答当然很棒。
也很容易看出，{1,2,3}中唯一可以让其平方有最后一位的数字是以个位数为9开头的数字。现在，如果我们使用9作为数字的最后一位数字：会平方到其中一个组合，我们很快就会发现，没有 10 的数字和个位数字 9 可以给出一个在其平方的第 10 位数字中涉及 {1,2,3} 的数字。
也许，这个解释回答了“300位数字与1,2和3的任意组合是否有平方根”之类的问题？
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"?