Write all solutions for a^3+b^3 = c^3 + d^3, where a, b, c, d lie between [0, 10^5].
编写所有解决方案b ^ ^ 3 + 3 = c ^ 3 + d ^ 3,,a,b,c,d隔[0,10 ^ 5]。
It's an interview question and I'm totally clueless.
这是一个面试问题，我完全没有头绪。
I'm thinking priority queues to at least iterate for a and b values. Some hint will be great, will try to work through from there.
我认为优先队列至少迭代a和b值。一些暗示将会很好，会尝试从那里开始。
9 个解决方案
#1
16
Using a hash map to store the (cube,(a,b)), you can iterate all possible pairs of integers, and output a solution once you have found that the required sum of cubes is already in the map.
使用散列映射来存储(多维数据集，(a,b))，您可以遍历所有可能的整数对，并且一旦发现所需的数据集总数已经在映射中，就可以输出一个解决方案。
pseudo code:
伪代码:
map <- empty hash_map<int,list<pair<int,int>>>
for each a in range(0,10^5):
for each b in range(a,10^5): //making sure each pair repeats only once
cube <- a^3 + b^3
if map.containsKey(cube):
for each element e in map.get(cube):
output e.first(), e.last(), a, b //one solution
else:
map.put(cube,new list<pair<int,int>>)
//for both cases, add the just found pair to the relevant list
map.get(cube).add(cube,new pair(a,b))
This solution is O(n^2) space(1) and O(n^2 + OUTPUT) time on average, where OUTPUT is the size of the output.
该解决方案是O(n 2)空间(1)和O(n 2 + OUTPUT)时间平均，其中输出为输出的大小。
EDIT:
编辑:
Required space is actually O(n^2 logn), where n is the range (10^5), because to represent 10^5 integers you need ceil(log_2(10^15)) = 50 bits. So, you actually need something like 500,000,000,000 bits (+ overhead for map and list) which is ~58.2 GB (+ overhead).
所需空间实际上是O(n ^ 2 logn),其中n是范围(10 ^ 5),因为代表10 ^ 5的整数你需要装天花板(log_2(10 ^ 15))= 50位。因此，您实际上需要大约500,000,000,000比特(用于map和list的开销)，即~58.2 GB(+开销)。
Since for most machines it is a bit too much - you might want to consider storing the data on disk, or if you have 64bits machine - just store in into "memory" and let the OS and virtual memory system do this as best as it can.
因为对于大多数机器来说，它有点太多了——您可能需要考虑将数据存储在磁盘上，或者如果您有64位的机器——只是存储在“内存”中，并让操作系统和虚拟内存系统尽可能做到最好。
(1) As the edit clarifies, it is actually O(n^2log(n)) space, however if we take each integer storage as O(1) (which is usually the case) we get O(n^2) space. Same principle will apply for the time complexity, obviously.
(1)编辑澄清,它实际上是O(n ^ 2 log(n))的空间,但是如果我们把每个整数存储为O(1)(通常是这样)O(n ^ 2)空间。显然，同样的原理也适用于时间复杂度。
#2
3
Using a priority queue is almost certainly the simplest solution, and also the most practical one, since it's O(n) storage (with a log factor if you require bignums). Any solution which involves computing all possible sums and putting them in a map will require O(n^2) storage, which soon becomes impractical.
使用优先级队列几乎可以肯定是最简单的解决方案，也是最实用的解决方案，因为它是O(n)存储(如果需要bignums，则使用日志因子)。任何解决方案涉及计算所有可能的资金,把它们在一个地图需要O(n ^ 2)存储,它很快变得不切实际。
My naive, non-optimized implementation using a priority queue is O(n^2 log(n)) time. Even so, it took less than five seconds for n = 10000 and about 750 seconds for n = 100000, using a couple of megabytes of storage. It certainly could be improved.
我的天真,未经优化的实现使用一个优先队列是O(n ^ 2 log(n))。即便如此，n = 10000的时候用时不到5秒，n = 100000的时间则是750秒，使用了几兆字节的存储空间。它当然可以改进。
The basic idea, as per your comment, is to initialize a priority queue with pairs (a, a+1) for a in the range [1, N), and then repeatedly increment the second value of the smallest (by sum of cubes) tuple until it reaches N. If at any time the smallest two elements in the queue are equal, you have a solution. (I could paste the code, but you only asked for a hint.)
的基本思想,根据你的评论,是初始化一个优先队列与双(a + 1)范围内(1,N),然后反复增加第二个值最小的(通过立方体之和)元组,直到达到最小的两个元素N .如果在任何时候队列是相等的,你有一个解决方案。(我可以粘贴代码，但你只需要提示。)
#3
1
A quicker than trivial solution is as follows: You calculate all values that a^3 + b^3 can have, and store all possible values of a and b with it. This is done by looping through a and b, storing the results (a^3 + b^3) in a binary tree and having a list of values (a's and b's) associated to each result.
更快比平凡解如下:计算所有值,b ^ ^ 3 + 3,A和b的和存储所有可能的值。这是通过循环a和b完成的，将结果存储在一个二叉树中，并有一个与每个结果相关联的值列表(a和b)。
After this step, you need to traverse the list and for each value, choose every possible assignment for a,b,c,d.
在此步骤之后，您需要遍历列表并为每个值选择每一个可能的任务，分别为a、b、c、d。
I think this solution takes O(n^2 log n) time and O(n^2) space, but i might be missing something.
我认为这个解需要O(n, 2 log n)时间和O(n 2)空间，但我可能漏掉了什么。
#4
1
int Search(){
int MAX = 10000000;
for(int a = 0; a < MAX; a++){
int a3 = a * a * a;
if(a3 > MAX) break;
for(int b = a; b < MAX; b ++){
int b3 = b * b * b;
if(a3 + b3 > MAX)break;
for(int c = 0; c < a; c++){
int c3 = c*c*c;
int m = a3 - c3;
int d = b+1;
while(true){
int d3 = d * d * d;
if(d3-b3 <= m){
if((d3 - b3) == m){
count++;
PUSH_Modified(a3, b3, c3, b3, a, b, c, d);
}
d++;
continue;
}
else
break;
}
}
}
}
return 0;
}
}
#5
1
Using Hashmap (O(n^2) solution):
使用Hashmap(O(n ^ 2)解决方案):
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import static java.lang.Math.pow;
/**
* Created by Anup on 10-10-2016.
*/
class Pair {
int a;
int b;
Pair(int x, int y) {
a = x;
b = y;
}
}
public class FindCubePair {
public static void main(String[] args) {
HashMap<Long, ArrayList<Pair>> hashMap = new HashMap<>();
int n = 100000;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
long sum = (long) (pow(i, 3) + pow(j, 3));
if(hashMap.containsKey(sum)) {
List<Pair> list = hashMap.get(sum);
for(Pair p : list) {
System.out.println(i + " " + j + " " + p.a + " " + p.b);
}
} else {
ArrayList<Pair> list = new ArrayList<>();
hashMap.put(sum, list);
}
hashMap.get(sum).add(new Pair(i, j));
}
}
}
}
Unfortunately, the value of integers printed does not even reach 1000 on my computer due to resource limitation.
不幸的是，由于资源限制，在我的计算机上打印的整数的值甚至不能达到1000。
#6
0
Let's assume a solution:
让我们假设一个解决方案:
a=A, b=B, c=C, and d=D.
a= a, b= b, c= c, d= d。
Given any solution we can generate another 3 solutions
给定任何解，我们可以生成另外3个解。
abcd
ABCD
ABDC
BACD
BADC
Actually, if A=B, or C=D, then we might only have 1 or 2 further solutions.
实际上，如果A=B，或者C=D，那么我们可能只有1或2个进一步的解。
We can choose the solutions we look for first by ordering A <= B and C <= D. This will reduce the search space. We can generate the missed solutions from the found ones.
我们可以通过点A <= B和C <= d来选择我们寻找的解决方案，这将减少搜索空间。我们可以从已找到的解决方案中生成遗漏的解决方案。
There will always be at least one solution, where A=C and B=D. What we're looking for is when A>C and B<D. This comes from the ordering: C can't be greater than A because, as we've chosen to only look at solutions where D>C, the cube sum would be too big.
总会有至少一个解，其中A=C和B=D。我们要找的是>C和B
We can calculate A^3 + B^3, put it in a map as the key, with a vector of pairs A,B as the value.
我们可以计算一个^ 3 + B ^ 3,把它放在一个地图的关键,与向量对A、B值。
There will be (n^2)/2 values.
会有(n ^ 2)/ 2的值。
If there are already values in the vector they will all have lower A and they are the solutions we're looking for. We can output them immediately, along with their permutations.
如果向量中已经有了值它们都有更低的A它们就是我们要找的解。我们可以立即输出它们，以及它们的排列。
I'm not sure about complexity.
我对复杂性不太确定。
#7
0
One Solution - using concept of finding 2 sum in a sorted array. This is O(n3)
一种解决方案——使用在排序数组中查找2和的概念。这是O(n3)
public static void pairSum() {
int SZ = 100;
long[] powArray = new long[SZ];
for(int i = 0; i< SZ; i++){
int v = i+1;
powArray[i] = v*v*v;
}
int countPairs = 0;
int N1 = 0, N2 = SZ-1, N3, N4;
while(N2 > 0) {
N1=0;
while(N2-N1 > 2) {
long ts = powArray[N1] + powArray[N2];
N3 = N1+1; N4 = N2-1;
while(N4 > N3) {
if(powArray[N4]+powArray[N3] < ts) {
N3++;
}else if(powArray[N4]+powArray[N3] > ts) {
N4--;
}else{
//System.out.println((N1+1)+" "+(N2+1)+" "+(N3+1)+" "+(N4+1)+" CUBE "+ts);
countPairs++;
break;
}
}
N1++;
}
N2--;
}
System.out.println("quadruplet pair count:"+countPairs);
}
#8
0
Logic :
a^3 + b^3 = c^3 + d^3
Then, a^3+b^3-c*3-d^3 = 0
Try to solve this equation by putting all combination of values for a,b,c and d in range of [0 , 10^5].
If equation is solved print the values of a,b,c and d
逻辑:^ 3 + b c ^ 3 + d ^ 3 ^ 3 =然后,^ 3 + b ^ 3 c * 3 d ^ 3 = 0尝试解决这个方程把所有的组合值,b,c和d的范围(0,10 ^ 5)。如果方程解出a、b、c和d的值。
public static void main(String[] args) {
//find all solutions of a^3 + b^3 = c^3 + d^3
double power = 3;
long counter = 0; // to count the number of solution sets obtained
int limit = 100000; // range from 0 to limit
//looping through every combination of a,b,c and d
for(int a = 0;a<=limit;a++)
{
for(int b = 0;b<=limit;b++)
{
for(int c = 0;c<=limit;c++)
{
for(int d = 0;d<=limit;d++)
{
// logic used : a^3 + b^3 = c^3 + d^3 can be written as a^3 + b^3 - c^3 - d^3 = 0
long result = (long)(Math.pow(a,power ) + Math.pow(b,power ) - Math.pow(c,power ) - Math.pow(d,power ));
if(result == 0 )
{
counter++; // to count the number of solutions
//printing the solution
System.out.println( "a = "+ a + " b = " + b + " c = " + c + " d = " + d);
}
}
}
}
}
//just to understand the change in number of solutions as limit and power changes
System.out.println("Number of Solutions =" + counter);
}
#9
0
Starting with the brute force approach, its pretty obvious it will O(n^4) time to execute. If space is not a constraint, we can go for combination of list and maps. The code is self-explanatory, we are using a nested list to keep track of all entries for a particular sum (key in map). The time complexity is thus reduced from O(n^4) to O(n^2)
从蛮力方法,很明显它将O(n ^ 4)时间来执行。如果空间不是约束，我们可以选择列表和映射的组合。代码是不言自明的，我们使用嵌套列表来跟踪特定和(map中的键)的所有条目。因此，时间复杂度从O(n 4)减少到O(n 2)
public void printAllCubes() {
int n = 50;
Map<Integer, ArrayList<ArrayList>> resMap = new HashMap<Integer, ArrayList<ArrayList>>();
ArrayList pairs = new ArrayList<Integer>();
ArrayList allPairsList = new ArrayList<ArrayList>();
for (int c = 1; c < n; c++) {
for (int d = 1; d < n; d++) {
int res = (int) (Math.pow(c, 3) + Math.pow(d, 3));
pairs.add(c);
pairs.add(d);
if (resMap.get(res) == null) {
allPairsList = new ArrayList<ArrayList>();
} else {
allPairsList = resMap.get(res);
}
allPairsList.add(pairs);
resMap.put(res, allPairsList);
pairs = new ArrayList<Integer>();
}
}
for (int a = 1; a < n; a++) {
for (int b = 1; b < n; b++) {
int result = (int) (Math.pow(a, 3) + Math.pow(b, 3));
ArrayList<ArrayList> pairList = resMap.get(result);
for (List p : pairList) {
System.out.print(a + " " + b + " ");
for (Object num : p)
System.out.print(num + " ");
System.out.println();
}
}
}
}
#1
16
Using a hash map to store the (cube,(a,b)), you can iterate all possible pairs of integers, and output a solution once you have found that the required sum of cubes is already in the map.
使用散列映射来存储(多维数据集，(a,b))，您可以遍历所有可能的整数对，并且一旦发现所需的数据集总数已经在映射中，就可以输出一个解决方案。
pseudo code:
伪代码:
map <- empty hash_map<int,list<pair<int,int>>>
for each a in range(0,10^5):
for each b in range(a,10^5): //making sure each pair repeats only once
cube <- a^3 + b^3
if map.containsKey(cube):
for each element e in map.get(cube):
output e.first(), e.last(), a, b //one solution
else:
map.put(cube,new list<pair<int,int>>)
//for both cases, add the just found pair to the relevant list
map.get(cube).add(cube,new pair(a,b))
This solution is O(n^2) space(1) and O(n^2 + OUTPUT) time on average, where OUTPUT is the size of the output.
该解决方案是O(n 2)空间(1)和O(n 2 + OUTPUT)时间平均，其中输出为输出的大小。
EDIT:
编辑:
Required space is actually O(n^2 logn), where n is the range (10^5), because to represent 10^5 integers you need ceil(log_2(10^15)) = 50 bits. So, you actually need something like 500,000,000,000 bits (+ overhead for map and list) which is ~58.2 GB (+ overhead).
所需空间实际上是O(n ^ 2 logn),其中n是范围(10 ^ 5),因为代表10 ^ 5的整数你需要装天花板(log_2(10 ^ 15))= 50位。因此，您实际上需要大约500,000,000,000比特(用于map和list的开销)，即~58.2 GB(+开销)。
Since for most machines it is a bit too much - you might want to consider storing the data on disk, or if you have 64bits machine - just store in into "memory" and let the OS and virtual memory system do this as best as it can.
因为对于大多数机器来说，它有点太多了——您可能需要考虑将数据存储在磁盘上，或者如果您有64位的机器——只是存储在“内存”中，并让操作系统和虚拟内存系统尽可能做到最好。
(1) As the edit clarifies, it is actually O(n^2log(n)) space, however if we take each integer storage as O(1) (which is usually the case) we get O(n^2) space. Same principle will apply for the time complexity, obviously.
(1)编辑澄清,它实际上是O(n ^ 2 log(n))的空间,但是如果我们把每个整数存储为O(1)(通常是这样)O(n ^ 2)空间。显然，同样的原理也适用于时间复杂度。
#2
3
Using a priority queue is almost certainly the simplest solution, and also the most practical one, since it's O(n) storage (with a log factor if you require bignums). Any solution which involves computing all possible sums and putting them in a map will require O(n^2) storage, which soon becomes impractical.
使用优先级队列几乎可以肯定是最简单的解决方案，也是最实用的解决方案，因为它是O(n)存储(如果需要bignums，则使用日志因子)。任何解决方案涉及计算所有可能的资金,把它们在一个地图需要O(n ^ 2)存储,它很快变得不切实际。
My naive, non-optimized implementation using a priority queue is O(n^2 log(n)) time. Even so, it took less than five seconds for n = 10000 and about 750 seconds for n = 100000, using a couple of megabytes of storage. It certainly could be improved.
我的天真,未经优化的实现使用一个优先队列是O(n ^ 2 log(n))。即便如此，n = 10000的时候用时不到5秒，n = 100000的时间则是750秒，使用了几兆字节的存储空间。它当然可以改进。
The basic idea, as per your comment, is to initialize a priority queue with pairs (a, a+1) for a in the range [1, N), and then repeatedly increment the second value of the smallest (by sum of cubes) tuple until it reaches N. If at any time the smallest two elements in the queue are equal, you have a solution. (I could paste the code, but you only asked for a hint.)
的基本思想,根据你的评论,是初始化一个优先队列与双(a + 1)范围内(1,N),然后反复增加第二个值最小的(通过立方体之和)元组,直到达到最小的两个元素N .如果在任何时候队列是相等的,你有一个解决方案。(我可以粘贴代码，但你只需要提示。)
#3
1
A quicker than trivial solution is as follows: You calculate all values that a^3 + b^3 can have, and store all possible values of a and b with it. This is done by looping through a and b, storing the results (a^3 + b^3) in a binary tree and having a list of values (a's and b's) associated to each result.
更快比平凡解如下:计算所有值,b ^ ^ 3 + 3,A和b的和存储所有可能的值。这是通过循环a和b完成的，将结果存储在一个二叉树中，并有一个与每个结果相关联的值列表(a和b)。
After this step, you need to traverse the list and for each value, choose every possible assignment for a,b,c,d.
在此步骤之后，您需要遍历列表并为每个值选择每一个可能的任务，分别为a、b、c、d。
I think this solution takes O(n^2 log n) time and O(n^2) space, but i might be missing something.
我认为这个解需要O(n, 2 log n)时间和O(n 2)空间，但我可能漏掉了什么。
#4
1
int Search(){
int MAX = 10000000;
for(int a = 0; a < MAX; a++){
int a3 = a * a * a;
if(a3 > MAX) break;
for(int b = a; b < MAX; b ++){
int b3 = b * b * b;
if(a3 + b3 > MAX)break;
for(int c = 0; c < a; c++){
int c3 = c*c*c;
int m = a3 - c3;
int d = b+1;
while(true){
int d3 = d * d * d;
if(d3-b3 <= m){
if((d3 - b3) == m){
count++;
PUSH_Modified(a3, b3, c3, b3, a, b, c, d);
}
d++;
continue;
}
else
break;
}
}
}
}
return 0;
}
}
#5
1
Using Hashmap (O(n^2) solution):
使用Hashmap(O(n ^ 2)解决方案):
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import static java.lang.Math.pow;
/**
* Created by Anup on 10-10-2016.
*/
class Pair {
int a;
int b;
Pair(int x, int y) {
a = x;
b = y;
}
}
public class FindCubePair {
public static void main(String[] args) {
HashMap<Long, ArrayList<Pair>> hashMap = new HashMap<>();
int n = 100000;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
long sum = (long) (pow(i, 3) + pow(j, 3));
if(hashMap.containsKey(sum)) {
List<Pair> list = hashMap.get(sum);
for(Pair p : list) {
System.out.println(i + " " + j + " " + p.a + " " + p.b);
}
} else {
ArrayList<Pair> list = new ArrayList<>();
hashMap.put(sum, list);
}
hashMap.get(sum).add(new Pair(i, j));
}
}
}
}
Unfortunately, the value of integers printed does not even reach 1000 on my computer due to resource limitation.
不幸的是，由于资源限制，在我的计算机上打印的整数的值甚至不能达到1000。
#6
0
Let's assume a solution:
让我们假设一个解决方案:
a=A, b=B, c=C, and d=D.
a= a, b= b, c= c, d= d。
Given any solution we can generate another 3 solutions
给定任何解，我们可以生成另外3个解。
abcd
ABCD
ABDC
BACD
BADC
Actually, if A=B, or C=D, then we might only have 1 or 2 further solutions.
实际上，如果A=B，或者C=D，那么我们可能只有1或2个进一步的解。
We can choose the solutions we look for first by ordering A <= B and C <= D. This will reduce the search space. We can generate the missed solutions from the found ones.
我们可以通过点A <= B和C <= d来选择我们寻找的解决方案，这将减少搜索空间。我们可以从已找到的解决方案中生成遗漏的解决方案。
There will always be at least one solution, where A=C and B=D. What we're looking for is when A>C and B<D. This comes from the ordering: C can't be greater than A because, as we've chosen to only look at solutions where D>C, the cube sum would be too big.
总会有至少一个解，其中A=C和B=D。我们要找的是>C和B
We can calculate A^3 + B^3, put it in a map as the key, with a vector of pairs A,B as the value.
我们可以计算一个^ 3 + B ^ 3,把它放在一个地图的关键,与向量对A、B值。
There will be (n^2)/2 values.
会有(n ^ 2)/ 2的值。
If there are already values in the vector they will all have lower A and they are the solutions we're looking for. We can output them immediately, along with their permutations.
如果向量中已经有了值它们都有更低的A它们就是我们要找的解。我们可以立即输出它们，以及它们的排列。
I'm not sure about complexity.
我对复杂性不太确定。
#7
0
One Solution - using concept of finding 2 sum in a sorted array. This is O(n3)
一种解决方案——使用在排序数组中查找2和的概念。这是O(n3)
public static void pairSum() {
int SZ = 100;
long[] powArray = new long[SZ];
for(int i = 0; i< SZ; i++){
int v = i+1;
powArray[i] = v*v*v;
}
int countPairs = 0;
int N1 = 0, N2 = SZ-1, N3, N4;
while(N2 > 0) {
N1=0;
while(N2-N1 > 2) {
long ts = powArray[N1] + powArray[N2];
N3 = N1+1; N4 = N2-1;
while(N4 > N3) {
if(powArray[N4]+powArray[N3] < ts) {
N3++;
}else if(powArray[N4]+powArray[N3] > ts) {
N4--;
}else{
//System.out.println((N1+1)+" "+(N2+1)+" "+(N3+1)+" "+(N4+1)+" CUBE "+ts);
countPairs++;
break;
}
}
N1++;
}
N2--;
}
System.out.println("quadruplet pair count:"+countPairs);
}
#8
0
Logic :
a^3 + b^3 = c^3 + d^3
Then, a^3+b^3-c*3-d^3 = 0
Try to solve this equation by putting all combination of values for a,b,c and d in range of [0 , 10^5].
If equation is solved print the values of a,b,c and d
逻辑:^ 3 + b c ^ 3 + d ^ 3 ^ 3 =然后,^ 3 + b ^ 3 c * 3 d ^ 3 = 0尝试解决这个方程把所有的组合值,b,c和d的范围(0,10 ^ 5)。如果方程解出a、b、c和d的值。
public static void main(String[] args) {
//find all solutions of a^3 + b^3 = c^3 + d^3
double power = 3;
long counter = 0; // to count the number of solution sets obtained
int limit = 100000; // range from 0 to limit
//looping through every combination of a,b,c and d
for(int a = 0;a<=limit;a++)
{
for(int b = 0;b<=limit;b++)
{
for(int c = 0;c<=limit;c++)
{
for(int d = 0;d<=limit;d++)
{
// logic used : a^3 + b^3 = c^3 + d^3 can be written as a^3 + b^3 - c^3 - d^3 = 0
long result = (long)(Math.pow(a,power ) + Math.pow(b,power ) - Math.pow(c,power ) - Math.pow(d,power ));
if(result == 0 )
{
counter++; // to count the number of solutions
//printing the solution
System.out.println( "a = "+ a + " b = " + b + " c = " + c + " d = " + d);
}
}
}
}
}
//just to understand the change in number of solutions as limit and power changes
System.out.println("Number of Solutions =" + counter);
}
#9
0
Starting with the brute force approach, its pretty obvious it will O(n^4) time to execute. If space is not a constraint, we can go for combination of list and maps. The code is self-explanatory, we are using a nested list to keep track of all entries for a particular sum (key in map). The time complexity is thus reduced from O(n^4) to O(n^2)
从蛮力方法,很明显它将O(n ^ 4)时间来执行。如果空间不是约束，我们可以选择列表和映射的组合。代码是不言自明的，我们使用嵌套列表来跟踪特定和(map中的键)的所有条目。因此，时间复杂度从O(n 4)减少到O(n 2)
public void printAllCubes() {
int n = 50;
Map<Integer, ArrayList<ArrayList>> resMap = new HashMap<Integer, ArrayList<ArrayList>>();
ArrayList pairs = new ArrayList<Integer>();
ArrayList allPairsList = new ArrayList<ArrayList>();
for (int c = 1; c < n; c++) {
for (int d = 1; d < n; d++) {
int res = (int) (Math.pow(c, 3) + Math.pow(d, 3));
pairs.add(c);
pairs.add(d);
if (resMap.get(res) == null) {
allPairsList = new ArrayList<ArrayList>();
} else {
allPairsList = resMap.get(res);
}
allPairsList.add(pairs);
resMap.put(res, allPairsList);
pairs = new ArrayList<Integer>();
}
}
for (int a = 1; a < n; a++) {
for (int b = 1; b < n; b++) {
int result = (int) (Math.pow(a, 3) + Math.pow(b, 3));
ArrayList<ArrayList> pairList = resMap.get(result);
for (List p : pairList) {
System.out.print(a + " " + b + " ");
for (Object num : p)
System.out.print(num + " ");
System.out.println();
}
}
}
}