Problem : print all +ve integer solution of the equation
a^3 + b^3 = c^3 + d^3
where a, b, c, d are integers bw 1 to 1000
Facing issue with Math.pow() function.
So I have written two code one is brute force and another one with a little optimisation. The first one is showing correct output while the 2nd one is not and this is due to the power function.
Math.pow(0,1/3) = 1 while it should be 0
class Find_a3_b3__c3_d3{
// final static int n = 100;
// solution 1 : BRUTE FORCE
public static void bruteForce(){ // O(N^4)
int n = 5;
int resultCount = 0;
for(int a=0; a<n ; a++){
for(int b=0; b<n; b++){
for(int c=0; c<n; c++){
for(int d=0; d<n; d++){
int a_3 = a*a*a;
int b_3 = b*b*b;
int c_3 = c*c*c;
int d_3 = d*d*d;
if(a_3 + b_3 == c_3 + d_3){
System.out.println((resultCount++) + " a: "+a +" b: "+b + " --- c: "+c + " d: "+d );
break;
}
}
}
}
}
System.out.println("\n\n");
}
// solution 2 : BRUTE FORCE
// idea is : as we know d is going to have one value for each pair of a,b & c so
// if we know a b & c , then we can find d by the relation cubeRoot (a_3 + b_3 - c_3);
public static void littleBetter(){ // O(N^4)
int n = 5;
int resultCount = 0;
for(int a=0; a<n ; a++){
for(int b=0; b<n; b++){
for(int c=0; c<n; c++){
int a_3 = a*a*a;
int b_3 = b*b*b;
int c_3 = c*c*c;
System.out.println(a +" " + b+" " + c +" ");
System.out.println(a_3 +" " + b_3+" " + c_3 +" " + Math.pow(a_3 + b_3 - c_3, 1/3));
int d = (int) Math.pow(a_3 + b_3 - c_3, 1/3);
int d_3 = d*d*d;
if(a_3 + b_3 == c_3 + d_3){
System.out.println((resultCount++) + " a: "+a +" b: "+b + " --- c: "+c + " d: "+d );
}
}
}
}
System.out.println("\n\n");
}
public static void main(String[] args) {
bruteForce();// O(n^4)
littleBetter(); // O(n^3)
System.out.println( Math.pow(0,1/3));
System.out.println( Math.pow(0,1));
System.out.println( Math.pow(0,0));
System.out.println( Math.pow(34,0));
System.out.println( Math.pow(34,-0));
System.out.println( Math.pow(0,1));
}
}
If you execute the program, you will see that the no of row of result are different too.
Output
🛑 ~/Documents/CTCI Codes >> javac Find_a3_b3__c3_d3.java
🛑 ~/Documents/CTCI Codes >> java Find_a3_b3__c3_d3
0 a: 0 b: 0 --- c: 0 d: 0
1 a: 0 b: 1 --- c: 0 d: 1
2 a: 0 b: 1 --- c: 1 d: 0
3 a: 0 b: 2 --- c: 0 d: 2
4 a: 0 b: 2 --- c: 2 d: 0
5 a: 0 b: 3 --- c: 0 d: 3
6 a: 0 b: 3 --- c: 3 d: 0
7 a: 0 b: 4 --- c: 0 d: 4
8 a: 0 b: 4 --- c: 4 d: 0
9 a: 1 b: 0 --- c: 0 d: 1
10 a: 1 b: 0 --- c: 1 d: 0
11 a: 1 b: 1 --- c: 1 d: 1
12 a: 1 b: 2 --- c: 1 d: 2
13 a: 1 b: 2 --- c: 2 d: 1
14 a: 1 b: 3 --- c: 1 d: 3
15 a: 1 b: 3 --- c: 3 d: 1
16 a: 1 b: 4 --- c: 1 d: 4
17 a: 1 b: 4 --- c: 4 d: 1
18 a: 2 b: 0 --- c: 0 d: 2
19 a: 2 b: 0 --- c: 2 d: 0
20 a: 2 b: 1 --- c: 1 d: 2
21 a: 2 b: 1 --- c: 2 d: 1
22 a: 2 b: 2 --- c: 2 d: 2
23 a: 2 b: 3 --- c: 2 d: 3
24 a: 2 b: 3 --- c: 3 d: 2
25 a: 2 b: 4 --- c: 2 d: 4
26 a: 2 b: 4 --- c: 4 d: 2
27 a: 3 b: 0 --- c: 0 d: 3
28 a: 3 b: 0 --- c: 3 d: 0
29 a: 3 b: 1 --- c: 1 d: 3
30 a: 3 b: 1 --- c: 3 d: 1
31 a: 3 b: 2 --- c: 2 d: 3
32 a: 3 b: 2 --- c: 3 d: 2
33 a: 3 b: 3 --- c: 3 d: 3
34 a: 3 b: 4 --- c: 3 d: 4
35 a: 3 b: 4 --- c: 4 d: 3
36 a: 4 b: 0 --- c: 0 d: 4
37 a: 4 b: 0 --- c: 4 d: 0
38 a: 4 b: 1 --- c: 1 d: 4
39 a: 4 b: 1 --- c: 4 d: 1
40 a: 4 b: 2 --- c: 2 d: 4
41 a: 4 b: 2 --- c: 4 d: 2
42 a: 4 b: 3 --- c: 3 d: 4
43 a: 4 b: 3 --- c: 4 d: 3
44 a: 4 b: 4 --- c: 4 d: 4
0 0 0
0 0 0 1.0
0 0 1
0 0 1 1.0
0 0 2
0 0 8 1.0
0 0 3
0 0 27 1.0
0 0 4
0 0 64 1.0
0 1 0
0 1 0 1.0
0 a: 0 b: 1 --- c: 0 d: 1
0 1 1
0 1 1 1.0
0 1 2
0 1 8 1.0
0 1 3
0 1 27 1.0
0 1 4
0 1 64 1.0
0 2 0
0 8 0 1.0
0 2 1
0 8 1 1.0
0 2 2
0 8 8 1.0
0 2 3
0 8 27 1.0
0 2 4
0 8 64 1.0
0 3 0
0 27 0 1.0
0 3 1
0 27 1 1.0
0 3 2
0 27 8 1.0
0 3 3
0 27 27 1.0
0 3 4
0 27 64 1.0
0 4 0
0 64 0 1.0
0 4 1
0 64 1 1.0
0 4 2
0 64 8 1.0
0 4 3
0 64 27 1.0
0 4 4
0 64 64 1.0
1 0 0
1 0 0 1.0
1 a: 1 b: 0 --- c: 0 d: 1
1 0 1
1 0 1 1.0
1 0 2
1 0 8 1.0
1 0 3
1 0 27 1.0
1 0 4
1 0 64 1.0
1 1 0
1 1 0 1.0
1 1 1
1 1 1 1.0
2 a: 1 b: 1 --- c: 1 d: 1
1 1 2
1 1 8 1.0
1 1 3
1 1 27 1.0
1 1 4
1 1 64 1.0
1 2 0
1 8 0 1.0
1 2 1
1 8 1 1.0
1 2 2
1 8 8 1.0
3 a: 1 b: 2 --- c: 2 d: 1
1 2 3
1 8 27 1.0
1 2 4
1 8 64 1.0
1 3 0
1 27 0 1.0
1 3 1
1 27 1 1.0
1 3 2
1 27 8 1.0
1 3 3
1 27 27 1.0
4 a: 1 b: 3 --- c: 3 d: 1
1 3 4
1 27 64 1.0
1 4 0
1 64 0 1.0
1 4 1
1 64 1 1.0
1 4 2
1 64 8 1.0
1 4 3
1 64 27 1.0
1 4 4
1 64 64 1.0
5 a: 1 b: 4 --- c: 4 d: 1
2 0 0
8 0 0 1.0
2 0 1
8 0 1 1.0
2 0 2
8 0 8 1.0
2 0 3
8 0 27 1.0
2 0 4
8 0 64 1.0
2 1 0
8 1 0 1.0
2 1 1
8 1 1 1.0
2 1 2
8 1 8 1.0
6 a: 2 b: 1 --- c: 2 d: 1
2 1 3
8 1 27 1.0
2 1 4
8 1 64 1.0
2 2 0
8 8 0 1.0
2 2 1
8 8 1 1.0
2 2 2
8 8 8 1.0
2 2 3
8 8 27 1.0
2 2 4
8 8 64 1.0
2 3 0
8 27 0 1.0
2 3 1
8 27 1 1.0
2 3 2
8 27 8 1.0
2 3 3
8 27 27 1.0
2 3 4
8 27 64 1.0
2 4 0
8 64 0 1.0
2 4 1
8 64 1 1.0
2 4 2
8 64 8 1.0
2 4 3
8 64 27 1.0
2 4 4
8 64 64 1.0
3 0 0
27 0 0 1.0
3 0 1
27 0 1 1.0
3 0 2
27 0 8 1.0
3 0 3
27 0 27 1.0
3 0 4
27 0 64 1.0
3 1 0
27 1 0 1.0
3 1 1
27 1 1 1.0
3 1 2
27 1 8 1.0
3 1 3
27 1 27 1.0
7 a: 3 b: 1 --- c: 3 d: 1
3 1 4
27 1 64 1.0
3 2 0
27 8 0 1.0
3 2 1
27 8 1 1.0
3 2 2
27 8 8 1.0
3 2 3
27 8 27 1.0
3 2 4
27 8 64 1.0
3 3 0
27 27 0 1.0
3 3 1
27 27 1 1.0
3 3 2
27 27 8 1.0
3 3 3
27 27 27 1.0
3 3 4
27 27 64 1.0
3 4 0
27 64 0 1.0
3 4 1
27 64 1 1.0
3 4 2
27 64 8 1.0
3 4 3
27 64 27 1.0
3 4 4
27 64 64 1.0
4 0 0
64 0 0 1.0
4 0 1
64 0 1 1.0
4 0 2
64 0 8 1.0
4 0 3
64 0 27 1.0
4 0 4
64 0 64 1.0
4 1 0
64 1 0 1.0
4 1 1
64 1 1 1.0
4 1 2
64 1 8 1.0
4 1 3
64 1 27 1.0
4 1 4
64 1 64 1.0
8 a: 4 b: 1 --- c: 4 d: 1
4 2 0
64 8 0 1.0
4 2 1
64 8 1 1.0
4 2 2
64 8 8 1.0
4 2 3
64 8 27 1.0
4 2 4
64 8 64 1.0
4 3 0
64 27 0 1.0
4 3 1
64 27 1 1.0
4 3 2
64 27 8 1.0
4 3 3
64 27 27 1.0
4 3 4
64 27 64 1.0
4 4 0
64 64 0 1.0
4 4 1
64 64 1 1.0
4 4 2
64 64 8 1.0
4 4 3
64 64 27 1.0
4 4 4
64 64 64 1.0
1.0
0.0
1.0
1.0
1.0
0.0
🛑 ~/Documents/CTCI Codes >>
When you divide two integers the answer becomes an integer too, that's because you get 1 instead of zero. 1/3 is equal to zero and Math.pow(0,0) is equal to 1. instead you can use Math.pow(0,1./3)) to get 0.
UPDATE
You can check this to see better solution that are already provided.