Найдите все идеальные квадраты, которые представляют собой перестановку примерно 300 цифр.
Это был вопрос, который недавно задали моему другу в интервью Google. Он не смог придумать решение, но все равно отказался от работы. Вот вопрос
Вам дали 300 цифр, состоящих из 100 единиц, 100 двоек и 100 троек, теперь придумайте алгоритм, который определит все такие числа, которые являются точным квадратом.
Я пробовал это некоторое время но я в тупике. Есть мысли о том, как это сделать?
1 ответ
Ответ n.m конечно же велик.
Также легко видеть, что единственным числом, у которого квадрат должен иметь последнюю цифру среди {1,2,3}, является число, начинающееся с единицы, равной 9. Теперь, если мы будем использовать 9 в качестве Последняя цифра числа, которая будет квадратной к одной из комбинаций, мы скоро увидим, что не существует ни 10-значный, ни 9-значный номер, который может дать число, включающее {1,2,3} в 10-й цифре его квадрата ,
Вероятно, это объяснение отвечает на такой вопрос, как «имеет ли любая комбинация из 300 цифр с 1,2 и 3 квадратный корень»?