Synthetic Transaction Monitoring that you need for the day to day, which ensures your business website keeps running optimally, and that there is no downtime to impact your customer experience.
Become a Premium Member and unlock a new, free course in leading technologies each month.
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;
}
}
Add your voice to the tech community where 5M+ people just like you are talking about what matters.
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(long input){
for(long i = 1; i < input; i*=2){
long product = i*i;
if (product == input){
System.out.println("power of 2: "+i/4);
return true;
}else if(product > input){
long lowerBound = i/2;
long 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/4+", high:" +high/4+", middle: "+mid/4);
product = mid*mid;
if(product == input){
System.out.println("other square: "+mid/4);
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.
If you are experiencing a similar issue, please ask a related question
Join the community of 500,000 technology professionals and ask your questions.