Запишем все решения для a ^ 3 + b ^ 3 = c ^ 3 + d ^ 3

Запишем все решения для a ^ 3 + b ^ 3 = c ^ 3 + d ^ 3, где a, b, c, d лежат между [0, 10 ^ 5].

Это вопрос интервью, и я совершенно не знаю.

Я думаю о приоритетных очередях, по крайней мере, для значений a и b. Какой-то намек будет замечательным, попробуем работать оттуда.

9 ответов

Используя хэш-карту для хранения (cube,(a,b)), вы можете перебирать все возможные пары целых чисел и вывести решение, как только обнаружите, что требуемая сумма кубов уже находится на карте.

псевдо-код:

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)) 
</pair<int,int></int,list<pair<int,int>

Это решение представляет собой O (n ^ 2) пространство (1) и O (n ^ 2 + OUTPUT) в среднем, где OUTPUT - это размер вывода.

EDIT:

Требуемое пространство на самом деле O(n^2 logn), где n - диапазон (10 ^ 5), потому что для представления целых чисел 10^5 вам нужны бит ceil(log_2(10^15)) = 50. Итак, вам действительно нужно что-то вроде 500 000 000 000 бит (+ накладные расходы для карты и списка), что составляет ~ 58,2 ГБ (+ накладные расходы).

Так как для большинства машин это слишком много - вы можете захотеть сохранить данные на диске или, если у вас есть 64-битная машина, просто сохраните в "память" и пусть ОС и виртуальная память делает это как можно лучше.

(1) По мере того, как редактирование поясняется, это фактически пространство O(n^2log(n)), однако если мы берем каждое целочисленное хранилище как O(1) (как правило, это так), мы получаем пробел O(n^2). Тот же принцип будет применяться для временной сложности, очевидно.


Использование очереди приоритетов - почти наверняка самое простое решение, а также наиболее практичное, так как это O (n) хранилище (с лог-фактором, если вам нужны бонусы). Любое решение, которое включает в себя вычисление всех возможных сумм и помещение их на карту, потребует хранения O (n ^ 2), что вскоре становится нецелесообразным.

Моя наивная, не оптимизированная реализация с использованием очереди приоритетов - это время O (n ^ 2 log (n)). Тем не менее, для n = 10000 и около 750 секунд для n = 100000 потребовалось меньше пяти секунд, используя пару мегабайт памяти. Это, безусловно, может быть улучшено.

Основная идея, согласно вашему комментарию, состоит в том, чтобы инициализировать очередь приоритета парами (a, a + 1) для a в диапазоне [1, N), а затем многократно увеличивать второе значение наименьшего (на сумма кубов) кортеж, пока не достигнет N. Если в любой момент наименьшие два элемента в очереди равны, у вас есть решение. (Я мог бы вставить код, но вы только попросили намек.)


Более быстрое, чем тривиальное решение: вы вычисляете все значения, которые может иметь a ^ 3 + b ^ 3, и сохраняйте все возможные значения a и b с ним. Это делается путем циклического перехода через a и b, сохраняя результаты (a ^ 3 + b ^ 3) в двоичном дереве и имея список значений (a и b), связанных с каждым результатом.

После этого шага вам нужно пройти по списку и для каждого значения, выбрать все возможные назначения для a, b, c, d.

Я думаю, что это решение занимает время O (n ^ 2 log n) и O (n ^ 2), но я мог бы что-то пропустить.


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;

}


Использование решения 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));
 }
 }
 }
}
</pair></pair></long,>

К сожалению, значение напечатанных целых чисел даже не достигает 1000 на моем компьютере из-за ограничения ресурсов.


Одно решение - использование понятия нахождения 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);
}


Начиная с подхода грубой силы, его довольно очевидно, что будет выполнено время O (n ^ 4). Если пространство не является ограничением, мы можем пойти на комбинацию списка и карт. Код не требует пояснений, мы используем вложенный список для отслеживания всех записей для конкретной суммы (ключ на карте). Таким образом, временная сложность уменьшается от 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();
 }
 }
 }
}
</arraylist></integer></arraylist></arraylist></integer></integer,></integer,>


Предположим, что решение:

a=A, b=B, c=C, and d=D.

Для любого решения мы можем сгенерировать еще 3 решения

abcd
ABCD
ABDC
BACD
BADC

Собственно, если A=B или C=D, тогда у нас может быть только 1 или 2 дополнительных решения.

Мы можем выбрать решения, которые мы ищем сначала, упорядочивая A <= B и C <= D. Это уменьшит пространство поиска. Мы можем генерировать пропущенные решения из найденных.

Всегда найдется хотя бы одно решение, где A=C и B=D. Мы ищем, когда A>C и B<d< code="">. Это происходит из упорядочения: <code>C не может быть больше A, потому что, поскольку мы решили посмотреть только на решения, где D>C, сумма куба была бы слишком большой.

<p>Мы можем вычислить <code>A^3 + B^3, поместить его в map в качестве ключа, а vector из пар A,B в качестве значения.

Будут (n^2)/2 значения.

Если в A, и они будут теми решениями, которые мы ищем. Мы можем выводить их немедленно, вместе с их перестановками.

Я не уверен в сложности.


Логика: a ^ 3 + b ^ 3 = c ^ 3 + d ^ 3 Тогда a ^ 3 + b ^ 3-c * 3-d ^ 3 = 0 Попробуйте решить это уравнение, поставив все комбинации значений для a, 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
 ****** 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);
 }

licensed under cc by-sa 3.0 with attribution.