Cracking The Coding Interview - выведите все положительные целочисленные решения уравнения

Question

В книге Cracking The Coding Interview

Есть пример:

Выведите все положительные целочисленные решения уравнения

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

, где a, b, c и d - целые числа от 1 до 1000.

Изображение

В книге говорится, что "мог работать только один", но я этого не понимаю.

Как я вижу, пока все эти переменные равны, это будет работать

Пример:

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

Answer 1

В качестве некой догадки (о чем вопрос?) Позвольте мне показать, как решить подобные проблемы (чтобы продемонстрировать это в интервью); вы совершенно правы, существует множество очевидных решений , например

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

Все, что нам нужно сделать, это установить a = c и b = d или a = d и b = c. Как насчет нетривиальных решений, подобных приведенным ниже?

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

Обратите внимание, что мы можем swap a и b или / и c и d, и у нас есть производное решение, подобное

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

, чтобы исключить их, допустим a <= b, c <= d и a < c

Наивный код с вложенными циклами (который упоминается в книге) длится слишком долго: у нас есть 1000 * 1000 * 1000 * 1000 = 1e12 операций для вычисления. Мы можем, однако, использовать встретить в середине технику и получить результат в доли секунды (с удалением двух внутренних петель):

1. Вычислить все a**3 + b**3 значения (только 1000 * 1000 = 1e6 операций - верхняя граница)
2. Группировать их
3. Отфильтровать интересные группы

C# код :

  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) });
    }
  }        

Теперь у нас есть cubes быть таким

  {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!
   ...

Время запроса групп:

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);

Результат:

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