Friday, November 7, 2014

Facebook: Write all solutions for a^3 + b^3 = c^3 + d^3, where a, b, c, d lie between [0, 10^5]

Facebook: Write all solutions for a^3 + b^3 = c^3 + d^3, where a, b, c, d lie between [0, 10^5]

Ramanujan's taxi. S. Ramanujan was an Indian mathematician who became famous for his intuition for numbers. When the English mathematician G. H. Hardy came to visit him in the hospital one day, Hardy remarked that the number of his taxi was 1729, a rather dull number. To which Ramanujan replied, "No, Hardy! No, Hardy! It is a very interesting number. It is the smallest number expressible as the sum of two cubes in two different ways." Verify this claim by writing a program Ramanujan.java that takes a command line argument N and prints out all integers less than or equal to N that can be expressed as the sum of two cubes in two different ways - find distinct positive integers abc, and d such that a3 + b3 = c3 + d3. Use four nested for loops.

Understand the problem:
The trick of the problem is to require that a, b, c, and d are different. In addition, a, b, c, and d lie between 0, 10^5

Naive Solution:
The most straight-forward solution would be iterate all possible combinations of a, b, c, and d. So the time complexity is O(n^4), and space is O(1).

Code (Java):
public class Solution {
    public void ramanujan(int n) {
        if (n <= 0) {
            return;
        }
        
        for (int a = 0; a < n; a++) {
            long a3 = a * a * a;
            for (int b = a + 1; b < n; b++) {
                long b3 = b * b * b;
                for (int c = a + 1; c < n; c++) {
                    long c3 = c * c * c;
                    for (int d = c + 1; d < n; d++) {
                        long d3 = d * d * d;
                        if (a3 + b3 == c3 + d3) {
                            System.out.println(a + "^3" + " + " + b + "^3" + 
                                               " = " + c + "^3" + " + " + d + "^3");
                        }
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
      Solution sol = new Solution();

      sol.ramanujan(100);
    }
}

A better Solution:
Use a hash table to store the a^3 + b^3 as the keys. If the second time that the a^3 + b^3 exists in the hash table, print out the results.

Code (Java):
import java.util.*;
public class Solution2 {
    public void ramanujan(int n) {
        if (n <= 0) {
            return;
        }
        
        Map<Long, List<Integer>> map = new HashMap<Long, List<Integer>>();
        
        for (int a = 1; a < n; a++) {
            for (int b = a + 1; b < n; b++) {
                long sum = a * a * a + b * b * b;
                if (map.containsKey(sum)) {
                    List<Integer> temp = map.get(sum);
                    System.out.println(temp.get(0) + "^3" + " + " + temp.get(1) + "^3" + " = " + 
                                       a + "^3" + " + " + b + "^3");
                } else {
                    List<Integer> temp = new ArrayList<Integer>();
                    temp.add(a);
                    temp.add(b);
                    map.put(sum, temp);
                }
            }
        }
    }

    public static void main(String[] args) {
      Solution2 sol = new Solution2();

      sol.ramanujan(100);
    }
}



2 comments:

  1. This comment has been removed by the author.

    ReplyDelete
  2. from collections import defaultdict
    def check(n):
    a= defaultdict(list)
    for i in range(0,n):
    for j in range(i+1,n):
    k = i**3 + j**3
    a[k] = a[k] + [(i,j)]


    for i,j in a.items():
    if len(j) > 2 :
    print i, j


    check(1729)

    ReplyDelete