Numero n Löydä kaksi paria, jotka voivat edustaa numeroa kahden kuution summana. Toisin sanoen löydä kaksi paria (a b) ja (c d) siten, että annettu numero n voidaan ilmaista
n = a^3 + b^3 = c^3 + d^3
missä b c ja d ovat neljä erillistä lukua.
Esimerkkejä:
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
Kaikilla rajoituksilla täytettävällä numerolla on kaksi erillistä paria (a b) ja (c d) siten, että a b c ja d ovat kaikki vähemmän kuin n1/3 . Idea on hyvin yksinkertainen. Jokaiselle erilliselle parille (x y), joka on muodostettu numeroilla vähemmän kuin n1/3 Jos niiden summa (x3+ ja3) on yhtä suuri kuin annettu numero Tallennamme ne hash -taulukkoon käyttämällä summaa avaimena. Jos parit, joiden summa on annettu lukumäärä, ilmestyy uudelleen, tulostamme vain molemmat parit.
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
Alla on yllä olevan idean toteutus -
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)
Lähtö:
(2 24) and (18 20)
Ajan monimutkaisuus yllä olevasta liuoksesta on O (n2/3) mikä on paljon vähemmän kuin O (n).
Voimmeko ratkaista yllä olevan ongelman O: ssa (n1/3) aika? Keskustelemme siitä seuraavassa viestissä.