With monday.com’s project management tool, you can see what everyone on your team is working in a single glance. Its intuitive dashboards are customizable, so you can create systems that work for you.
public class PerfectSquare{
public static void main(String[] args){
System.out.println(isPerfectSquare(Integer.parseInt(args[0])));
// MAX int value: 2147483647 = 2^31-1
// But, the maximum value I am able to work with is 2^30, larger numbers below MAX do not throw error but stall.
}
public static boolean isPerfectSquare(int input){
for(int i = 1; i < input; i*=2){
int product = i*i;
if (product == input){
System.out.println("power of 2: "+i);
return true;
}else if(product > input){
int lowerBound = i/2;
int upperBound = i;
return binarySearch(lowerBound, upperBound, input);
}
}
return false;
}
public static boolean binarySearch(int low, int high, int input){
int mid, product, ans = 0;
while (low <= high) {
mid = (low + high) / 2;
System.out.println("low: "+low+", high:" +high+", middle: "+mid);
product = mid*mid;
if(product == input){
System.out.println("other square: "+mid);
ans = 1;
break;
} else if (product > input) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return ans == 1 ? true : false;
}
}
I don't understand why long works and int doesn't. long is 32bit, and int is 64bit,
then i*i > 2^32
conclusion: my algorithm is crappy,
public static boolean isPerfectSquare(int input){
for(int i = 1; i < input; i*=2){
long product = (long)i*i;
System.out.println("Product " + product);
if (product == input){
System.out.println("power of 2: "+i);
return true;
}else if(product > (long)input){
int lowerBound = i/2;
int upperBound = i;
return binarySearch(lowerBound, upperBound, input);
}
}
return false;
}
public static boolean binarySearch(long low, long high, long input){
long mid, product, ans = 0;
while (low <= high) {
mid = (low + high) / 2;
System.out.println("low: "+low+", high:" +high+", middle: "+mid);
product = mid*mid;
if(product == input){
System.out.println("other square: "+mid);
ans = 1;
break;
} else if (product > input) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return ans == 1 ? true : false;
}
If you simply switch to longs then the method works fine for me:
class inttest{
static int i=0;
public static void main(String[] args){
System.out.println(Integer.parseInt(args[0]));
i=Integer.parseInt(args[0])+1;
System.out.println(i);
}
}
class inttest{
static int i=0;
static long l =0;
public static void main(String[] args){
if (Integer.parseInt(args[0])<2147483647) {args[0]="2147483647";}
System.out.println(Integer.parseInt(args[0]));
i=Integer.parseInt(args[0])+1;
System.out.println(i);
l= (long)i;
try{
while (l<Long.MAX_VALUE&&l>Long.MIN_VALUE){
l *= 2;
System.out.println(l);
}
}catch(Exception e){}
}
}
If I haven't upset Doug, he might help further, but my money says that whatever type you use, it's finite and will overrun sometime.
Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.
Have a better answer? Share it in a comment.
Open in new window