Drastically shorten your training time with WalkMe's advanced online training solution that Guides your trainees to action. Forget about retraining and skyrocket knowledge retention rates.
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
Title | # Comments | Views | Activity |
---|---|---|---|
ejb entity bean example | 2 | 39 | |
SequenceInputStream example | 3 | 23 | |
Eclipse Java import and method not resolved | 4 | 82 | |
Given a github repo find email address of all collaborators in that repo | 1 | 36 |
Join the community of 500,000 technology professionals and ask your questions.