Trobeu parells de cubs | Conjunt 1 (A n^(2/3) Solució)
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 n 1/3 . La idea és molt senzilla. Per a cada parella diferent (x y) formada per nombres menys que el n 1/3 Si la seva suma (x 3 + i 3 ) é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 = n 1/3 3) for (int x = 1; x < cubeRoot; x++) for (int y = x + 1; y <= cubeRoot; y++) int sum = x 3 + y 3 ; 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++ program to find pairs that can represent // the given number as sum of two cubes #include using namespace std ; // Function to find pairs that can represent // the given number as sum of two cubes void findPairs ( int n ) { // find cube root of n int cubeRoot = pow ( n 1.0 / 3.0 ); // create an empty map unordered_map < int pair < int int > > s ; // 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 . find ( sum ) != s . end ()) { cout < < '(' < < s [ sum ]. first < < ' ' < < s [ sum ]. second < < ') and (' < < x < < ' ' < < y < < ')' < < endl ; } else // if sum is seen for the first time s [ sum ] = make_pair ( x y ); } } } // Driver function int main () { int n = 13832 ; findPairs ( n ); return 0 ; }
Java // 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 # 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# // 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 // 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 (n 2/3 ) que és molt inferior a O (n).
Podem resoldre el problema anterior a O (n 1/3 ) temps? Ho discutirem a la propera publicació.
