Найдите все идеальные квадраты, которые являются перестановкой примерно 300 цифр

Это был вопрос, который был задан моему другу в интервью Google некоторое время назад. Он не смог придумать решение, но все равно закончил работу. Здесь вопрос

Вам дано 300 цифр, состоящих из 100 единиц, 100 двойников и 100 т., теперь выработал алгоритм, который определит все такие числа, которые являются идеальным квадратом

Я пробовал это некоторое время, но я в тупике. Любые мысли о том, как это сделать?

Ответы

Ответ 1

   printf ("{}\n");

Заданное множество пусто (сумма цифр делится на 3, но не на 9).

Ответ 2

n.m ответ, конечно, замечательный.

Также легко видеть, что единственное число, которое может иметь свой квадрат, имеет последнюю цифру среди {1,2,3} - число, начинающееся с цифры единицы как 9. Теперь, если мы используем 9 как последнюю цифру число, которое было бы квадратным для одной из комбинаций, мы скоро увидим, что нет 10 цифр вместе с 9 единицей, которая может дать число, включающее {1,2,3} в 10-й цифре его квадрата.

Возможно, это объяснение отвечает на вопрос типа "любая комбинация из 300 цифр с 1,2 и 3 имеет квадратный корень"?