Vzhľadom na číslo n nájdite dva páry, ktoré môžu predstavovať číslo ako súčet dvoch kociek. Inými slovami, nájdite dva páry (A B) a (c d) tak, aby dané číslo n bolo možné vyjadriť ako
ako používať pracovný stôl mysql
n = a^3 + b^3 = c^3 + d^3
kde B C a D sú štyri odlišné čísla.
Príklady:
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
Akékoľvek číslo n, ktoré vyhovuje obmedzeniu, bude mať dva odlišné páry (A B) a (c d) tak, že A B C a D sú nižšie n1/3 . Myšlienka je veľmi jednoduchá. Pre každý odlišný pár (x y) tvorený číslami menšími ako n1/3 Ak ich suma (x3+ a3) sa rovná danému číslu, ktoré ukladáme v tabuľke hash pomocou súčtu ako kľúč. Ak sa páry so súčtom rovnajú danému číslu, znova, jednoducho vytlačíme oba páry.
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
Nižšie je uvedená implementácia vyššie uvedenej myšlienky -
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)
Výstup:
(2 24) and (18 20)
Zložitosť vyššie uvedeného roztoku je O (n2/3), ktorý je oveľa menší ako O (n).
Môžeme vyriešiť vyššie uvedený problém v O (n1/3) čas? Budeme o tom diskutovať v nasledujúcom príspevku.