Напишите все решения для 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))
Это решение в среднем составляет O(n^2) пробела(1) и O(n^2 + OUTPUT), где OUTPUT - размер выходного сигнала.
РЕДАКТИРОВАТЬ:
Требуемое пространство на самом деле 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) хранилище (с логарифмическим коэффициентом, если вам требуются bignums). Любое решение, которое включает в себя вычисление всех возможных сумм и размещение их на карте, потребует хранения O(n^2), что вскоре становится непрактичным.
Моя наивная, неоптимизированная реализация, использующая очередь приоритетов, - O(n^2 log(n)) время. Тем не менее, это заняло менее пяти секунд при n = 10000 и около 750 секунд при n = 100000 при использовании нескольких мегабайт памяти. Это, безусловно, может быть улучшено.
Основная идея, согласно вашему комментарию, состоит в том, чтобы инициализировать приоритетную очередь парами (a, a+1) для a в диапазоне [1, N), а затем многократно увеличивать второе значение наименьшего (суммой кубов).) кортеж, пока не достигнет N. Если в любой момент два самых маленьких элемента в очереди равны, у вас есть решение. (Я мог вставить код, но вы только попросили подсказку.)
Используя решение 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 на моем компьютере из-за ограниченности ресурсов.
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;
}
Более быстрое, чем тривиальное решение, выглядит следующим образом: Вы вычисляете все значения, которые может иметь ^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) пространства, но я мог бы что-то упустить.
Одно из решений - использование концепции нахождения 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);
}
Давайте предположим решение:
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 ценности.
Если уже есть значения в vector они все будут ниже A и они являются решениями, которые мы ищем. Мы можем вывести их немедленно, вместе с их перестановками.
Я не уверен насчет сложности.
Логика:
а ^3 + б ^3 = с ^3 + д ^ 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);
}
Начиная с подхода грубой силы, довольно очевидно, что у него будет 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();
}
}
}
}