NumberFun
Categories:
You might know some pretty large perfect squares. But what about the NEXT one?
Complete the findNextSquare method that finds the next integral perfect square after the one passed as a parameter. Recall that an integral perfect square is an integer n such that sqrt(n) is also an integer.
If the argument is itself not a perfect square then return either -1 or an empty value like None or null, depending on your language. You may assume the argument is non-negative.
https://www.codewars.com/kata/56269eb78ad2e4ced1000013
To be honest, there is no better way to utilize hardware instructions than by designing an algorithm yourself.
However, we can use an existing algorithm here.
public static long findNextSquare(long sq) {
// perfect number should end with 0, 9, 5, 4, 1
int back = (int)(sq % 10);
// indicate input is perfect square or not
if(back != 0 && back != 9 && back != 5 && back != 4 && back != 1 && back != 6){
return -1L;
}
// maybe a perfect number
else{
// find square root
// use repeated substraction
int factor = 1, i = 0;
while(sq > 0){
sq -= factor;
i++;
factor += 2;
}
long sqrt = i+1;
if(sq == 0) return sqrt*sqrt;
else return -1L;
}
}
Test cases
@Test
public void test1() {
assertEquals(144, NumberFun.findNextSquare(121));
}
@Test
public void test2() {
assertEquals(-1, NumberFun.findNextSquare(155));
}
@Test
public void test3() {
assertEquals(320356, NumberFun.findNextSquare(319225));
}
@Test
public void test4() {
assertEquals(15241630849L, NumberFun.findNextSquare(15241383936L));
}
@Test
public void test5() {
assertEquals(-1, NumberFun.findNextSquare(342786627));
}
@Test
public void randomTest1() {
long input = (long)(Math.random()*100000L)+1;
long square = input*input;
assertEquals(square+(input*2+1), NumberFun.findNextSquare(square));
}
The key part is type conversion—we need to convert int to long. Be careful, as the result of our calculation may exceed the range of int.
For example:
return (long) * (long);
is different from
return (long)(int * int);
The latter may cause a loss of accuracy.