Tenint en compte un número n, trobeu dues parelles que poden representar el nombre com a suma de dos cubs. Dit d'una altra manera, trobeu dues parelles (a b) i (c d) de manera que es pot expressar el número N donat com a
n = a^3 + b^3 = c^3 + d^3
on a b c i d són quatre nombres diferents.
Exemples:
Input: N = 1729 Output: (1 12) and (9 10) Explanation: 1729 = 1^3 + 12^3 = 9^3 + 10^3 Input: N = 4104 Output: (2 16) and (9 15) Explanation: 4104 = 2^3 + 16^3 = 9^3 + 15^3 Input: N = 13832 Output: (2 24) and (18 20) Explanation: 13832 = 2^3 + 24^3 = 18^3 + 20^3
Qualsevol nombre n que satisfà la restricció tindrà dues parelles diferents (a b) i (c d) de manera que a b c i d siguin menys de n1/3 . La idea és molt senzilla. Per a cada parella diferent (x y) formada per nombres menys que el n1/3 Si la seva suma (x3+ i3) és igual al nombre donat que els emmagatzemem a una taula de hash mitjançant la suma com a clau. Si apareixen parells amb suma igual al número donat, simplement imprimim ambdues parelles.
1) Create an empty hash map say s. 2) cubeRoot = n1/3 3) for (int x = 1; x < cubeRoot; x++) for (int y = x + 1; y <= cubeRoot; y++) int sum = x3 + y3; if (sum != n) continue; if sum exists in s we found two pairs with sum print the pairs else insert pair(x y) in s using sum as key
A continuació es mostra la implementació de la idea anterior:
C++
// C++ program to find pairs that can represent // the given number as sum of two cubes #include
// Java program to find pairs that can represent // the given number as sum of two cubes import java.util.*; class GFG { static class pair { int first second; public pair(int first int second) { this.first = first; this.second = second; } } // Function to find pairs that can represent // the given number as sum of two cubes static void findPairs(int n) { // find cube root of n int cubeRoot = (int) Math.pow(n 1.0/3.0); // create an empty map HashMap<Integer pair> s = new HashMap<Integer pair>(); // Consider all pairs such with values less // than cuberoot for (int x = 1; x < cubeRoot; x++) { for (int y = x + 1; y <= cubeRoot; y++) { // find sum of current pair (x y) int sum = x*x*x + y*y*y; // do nothing if sum is not equal to // given number if (sum != n) continue; // if sum is seen before we found two pairs if (s.containsKey(sum)) { System.out.print('(' + s.get(sum).first+ ' ' + s.get(sum).second+ ') and (' + x+ ' ' + y+ ')' +'n'); } else // if sum is seen for the first time s.put(sum new pair(x y)); } } } // Driver code public static void main(String[] args) { int n = 13832; findPairs(n); } } // This code is contributed by PrinciRaj1992
# Python3 program to find pairs # that can represent the given # number as sum of two cubes # Function to find pairs that # can represent the given number # as sum of two cubes def findPairs(n): # Find cube root of n cubeRoot = pow(n 1.0 / 3.0); # Create an empty map s = {} # Consider all pairs such with # values less than cuberoot for x in range(int(cubeRoot)): for y in range(x + 1 int(cubeRoot) + 1): # Find sum of current pair (x y) sum = x * x * x + y * y * y; # Do nothing if sum is not equal to # given number if (sum != n): continue; # If sum is seen before we # found two pairs if sum in s.keys(): print('(' + str(s[sum][0]) + ' ' + str(s[sum][1]) + ') and (' + str(x) + ' ' + str(y) + ')' + 'n') else: # If sum is seen for the first time s[sum] = [x y] # Driver code if __name__=='__main__': n = 13832 findPairs(n) # This code is contributed by rutvik_56
// C# program to find pairs that can represent // the given number as sum of two cubes using System; using System.Collections.Generic; class GFG { class pair { public int first second; public pair(int first int second) { this.first = first; this.second = second; } } // Function to find pairs that can represent // the given number as sum of two cubes static void findPairs(int n) { // find cube root of n int cubeRoot = (int) Math.Pow(n 1.0/3.0); // create an empty map Dictionary<int pair> s = new Dictionary<int pair>(); // Consider all pairs such with values less // than cuberoot for (int x = 1; x < cubeRoot; x++) { for (int y = x + 1; y <= cubeRoot; y++) { // find sum of current pair (x y) int sum = x*x*x + y*y*y; // do nothing if sum is not equal to // given number if (sum != n) continue; // if sum is seen before we found two pairs if (s.ContainsKey(sum)) { Console.Write('(' + s[sum].first+ ' ' + s[sum].second+ ') and (' + x+ ' ' + y+ ')' +'n'); } else // if sum is seen for the first time s.Add(sum new pair(x y)); } } } // Driver code public static void Main(String[] args) { int n = 13832; findPairs(n); } } // This code is contributed by PrinciRaj1992
// JavaScript program to find pairs that can represent // the given number as sum of two cubes // Function to find pairs that can represent // the given number as sum of two cubes function findPairs(n){ // find cube root of n let cubeRoot = Math.floor(Math.pow(n 1/3)); // create an empty map let s = new Map(); // Consider all pairs such with values less // than cuberoot for (let x = 1; x < cubeRoot; x++){ for (let y = x + 1; y <= cubeRoot; y++){ // find sum of current pair (x y) let sum = x*x*x + y*y*y; // do nothing if sum is not equal to // given number if (sum != n){ continue; } // if sum is seen before we found two pairs if (s.has(sum)){ console.log('(' s.get(sum)[0] '' s.get(sum)[1] ') and ('x'' y')'); } else{ // if sum is seen for the first time s.set(sum [x y]); } } } } // Driver function { let n = 13832; findPairs(n); } // The code is contributed by Gautam goel (gautamgoel962)
Sortida:
(2 24) and (18 20)
Complexitat temporal de la solució anterior és O (n2/3) que és molt inferior a O (n).
Podem resoldre el problema anterior a O (n1/3) temps? Ho discutirem a la propera publicació.