Runtime of classic Cracking the Coding Interview question a^3 + b^3 = c^3 + d^3?

Question

Hi I am going over Gayle Laakmann's CTIC book and I came across her question

print all possible integer solutions for a^3 + b^3 = c^3 + d^3 where a,b,c,d can be integers 1 - 1000

She gave some pseudo code which looks like this:

First solution

n = 1000
for c from 1 to n
   for d from 1 to n
      result = c^3 + d^3
      append(c,d) to list at value map[result]

for a from 1 to n
   for b from 1 to n
      result = a^3 + b^3
      list = map.get(result)
      for each pair in list
         print a, b, pair

Second Solution

n = 1000
for c from 1 to n
   for d from 1 to n
      result = c^3 + d^3
      append (c,d) to list at value map[result]

for each result, list in map
   for each pair1 in list
      for each pair2 in list
         print pair1, pair2

How do any of these solutions get an O(n^2) running time? Even in the first solution the second set of for loops you also iterate over the pairs in your map so wouldn't that be O(n^3)?

I think it depends on the asymptotics of [this OEIS sequence](https://oeis.org/A173677). I did a quick search but didn't find anything useful; there might not be a known tight bound on the asymptotic growth rate. That said, the max up to 10,000 is 4 ways (and that's including 0 as a cube), so at least for the range up to 1,000 the running time should be roughly quadratic. — kaya3, Feb 10 '20 at 04:31
That said, the max up to 10,000 is 4 ways (and that's including 0 as a cube), so at least for the range up to 1,000 the running time should be roughly quadratic. — kaya3, Feb 10 '20 at 04:38
The solution by Manoj is incorrect as it excludes all those integers that can be written as the sum of two positive cubes in 3 different ways. (Such numbers do exist when n = 1000). Reasoning about any algorithm to solve this problem requires reasoning about the number of ways sums of two cubes can be written as sums of two other cubes. — box_of_donuts, Feb 10 '20 at 17:56
@box_of_donuts thanks for the correction, i removed my answer. — User_67128, Feb 10 '20 at 19:09
Check if this help https://stackoverflow.com/questions/44859599/solving-a3-b4-c3-d3-best-runtime — Marcio J, Apr 21 '22 at 00:33

walnut · Answer 1 · 2020-02-16T01:23:12.077

If r(m) is the number of ordered representations of m as the sum of two positive integer cubes, then it is known that sum(r(m)^2, m=0..M) is Theta(M^(2/3)), see ^[1].

This implies that the number of solutions your algorithm will print is O(n^2), because the largest possible sum of two cubes you will generate is 2*N^3 and the maximum number of solutions for a given m is r(m)^2 to account for all combinations of the representations on both sides of the equation.

Because the innermost loop always iterates exactly ones per printed result, it is then also only executed at most O(n^2) times, making the whole algorithm Theta(n^2) (due to the outer loops iteration time).

^[1] Hooley (1963): On the representations of a number as the sum of two cubes; https://link.springer.com/article/10.1007/BF01111429

Runtime of classic Cracking the Coding Interview question a^3 + b^3 = c^3 + d^3?

1 Answers1