Вот решение «разделяй и властвуй».
Если квадратный корень из натурального числа (number) является натуральным числом (solution), вы можете легко определить диапазон для solution на основе количества цифр number:
number имеет 1 цифру: solution в диапазоне = 1 - 4 number имеет 2 цифры: solution в диапазоне = 3 - 10 number имеет 3 цифры: solution в диапазоне = 10 - 40 number имеет 4 цифры: solution в диапазоне = 30 - 100 number имеет 5 цифр: solution в диапазоне = 100 - 400
Заметили повторение?
Вы можете использовать этот диапазон в подходе двоичного поиска, чтобы увидеть, существует ли solution, для которого:
number == solution * solution
Вот код
Вот мой класс SquareRootChecker
public class SquareRootChecker {
private long number;
private long initialLow;
private long initialHigh;
public SquareRootChecker(long number) {
this.number = number;
initialLow = 1;
initialHigh = 4;
if (Long.toString(number).length() % 2 == 0) {
initialLow = 3;
initialHigh = 10;
}
for (long i = 0; i < Long.toString(number).length() / 2; i++) {
initialLow *= 10;
initialHigh *= 10;
}
if (Long.toString(number).length() % 2 == 0) {
initialLow /= 10;
initialHigh /=10;
}
}
public boolean checkSquareRoot() {
return findSquareRoot(initialLow, initialHigh, number);
}
private boolean findSquareRoot(long low, long high, long number) {
long check = low + (high - low) / 2;
if (high >= low) {
if (number == check * check) {
return true;
}
else if (number < check * check) {
high = check - 1;
return findSquareRoot(low, high, number);
}
else {
low = check + 1;
return findSquareRoot(low, high, number);
}
}
return false;
}
}
А вот пример того, как его использовать.
long number = 1234567;
long square = number * number;
SquareRootChecker squareRootChecker = new SquareRootChecker(square);
System.out.println(square + ": " + squareRootChecker.checkSquareRoot()); //Prints "1524155677489: true"
long notSquare = square + 1;
squareRootChecker = new SquareRootChecker(notSquare);
System.out.println(notSquare + ": " + squareRootChecker.checkSquareRoot()); //Prints "1524155677490: false"