Запишем все решения для a ^ 3 + b ^ 3 = c ^ 3 + d ^ 3, где a, b, c, d лежат между [0, 10 ^ 5].
Это вопрос интервью, и я совершенно не знаю.
Я думаю о приоритетных очередях, по крайней мере, для значений a и b. Какой-то намек будет замечательным, попробуем работать оттуда.
Используя хэш-карту для хранения (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))
Это решение представляет собой 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));
}
}
}
}
К сожалению, значение напечатанных целых чисел даже не достигает 1000 на моем компьютере из-за ограничения ресурсов.
Предположим, что решение:
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. Это происходит из упорядочения: C не может быть больше A, потому что, поскольку мы решили посмотреть только на решения, где D>C, сумма куба была бы слишком большой.
Мы можем вычислить A^3 + B^3, поместить его в map в качестве ключа, а vector из пар A,B в качестве значения.
Будут (n^2)/2 значения.
Если в A, и они будут теми решениями, которые мы ищем. Мы можем выводить их немедленно, вместе с их перестановками.
Я не уверен в сложности.
Одно решение - использование понятия нахождения 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();
}
}
}
}
Логика:
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
double 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);
}