CODEWITHSUNDEEP
algorithm
Sitha
Sitha

Reputation: 51

Cracking The Coding Interview - Print all positive integer solutions to the equation

In the book Cracking The Coding Interview

There is an example:

Print all positive integer solutions to the equation

a^3 + b^3 = c^3 + d^3

where a, b, c, and d are integers between 1 and 1000.

Image

In the book it states that "only one could work", but I don't get that.

As I can see, as long as all those variables are equal, it will work

Example:

a = 1, b = 1, c = 1, d = 1
a = 2, b = 2, c = 2, d = 2
a = 3, b = 3, c = 3, d = 3

Upvotes: 3

Views: 936

Answers (1)

Dmitrii Bychenko
Dmitrii Bychenko

Reputation: 186803

As a kind of guess (what is the question about?) let me show how to solve these kind of problems (in order to demonstrate it in the interview); you are quite right, there are a lot of evident solutions, like

  1**3 + 1**3 = 1**3 + 1**3
  1**3 + 2**3 = 2**3 + 1**3

All we have to do is to set a = c and b = d or a = d and b = c. What about non-trivial solutions like those below?

   1**3 +  12**3 =   9**3 +  10**3
  84**3 + 280**3 = 217**3 + 231**3

Please note, that we can swap a and b or / and c and d, and have a derivative solution like

  12**3 + 1**3 = 10**3 + 9**3

to exclude them let's assume a <= b, c <= d and a < c

Naive code with nested loops (which is mentioned in the book) lasts too long: we have 1000 * 1000 * 1000 * 1000 = 1e12 operations to compute. We can, however, use meet in the middle technique and have the result in a fraction of a second (with two inmost loops removed):

  1. Compute all a**3 + b**3 values (just 1000 * 1000 = 1e6 operations - upper bound)
  2. Group them
  3. Filter out interesting groups

C# code:

  Dictionary<long, List<(long, long)>> cubes = new Dictionary<long, List<(long, long)>>();

  for (long a = 1; a < 1000; ++a) {
    long a3 = a * a * a;

    for (long b = a; b < 1000; ++b) {
      long key = b * b * b + a3;

      if (cubes.TryGetValue(key, out var list))
        list.Add((a, b));
      else
        cubes.Add(key, new List<(long, long)>() { (a, b) });
    }
  }

Now we have cubes be like this

  {2, {(1, 1)}} // group with one (a, b) pair
  {9, {(1, 2)}} // another group with one (a, b) pair
   ...
  {1729, {(1, 12), (9, 10)}} // <- the group we are looking for!
   ...

Time to query the groups: 

var report = string.Join(Environment.NewLine, cubes
  .Where(pair => pair.Value.Count >= 2)
  .Select(pair => $"{string.Join(" = ", pair.Value.Select(t => $"{t.Item1}**3 + {t.Item2}**3"))}"));

Console.Write(report);

Outcome:

1**3 + 12**3 = 9**3 + 10**3
1**3 + 103**3 = 64**3 + 94**3
1**3 + 150**3 = 73**3 + 144**3
1**3 + 249**3 = 135**3 + 235**3
... 
22**3 + 986**3 = 180**3 + 984**3 = 692**3 + 856**3
...
802**3 + 987**3 = 883**3 + 924**3

Upvotes: 2

Related Questions