Găsiți perechi de cuburi | Set 1 (a n^(2/3) soluție)
Având în vedere un număr n, găsiți două perechi care pot reprezenta numărul ca sumă de doi cuburi. Cu alte cuvinte, găsiți două perechi (A B) și (C D) astfel încât numărul N dat poate fi exprimat ca
n = a^3 + b^3 = c^3 + d^3
unde A B C și D sunt patru numere distincte.
Exemple:
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
Orice număr n care satisface constrângerea va avea două perechi distincte (A B) și (C D) astfel încât A B C și D sunt mai mici decât n 1/3 . Ideea este foarte simplă. Pentru fiecare pereche distinctă (x y) formată din numere mai mici decât n 1/3 Dacă suma lor (x 3 + și 3 ) este egal cu numărul dat, le stocăm într -un tabel de hash folosind suma ca cheie. Dacă perechile cu sumă egală cu numărul dat apare din nou, pur și simplu tipărește ambele perechi.
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
Mai jos este implementarea ideii de mai sus -
// 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)
Ieșire:
(2 24) and (18 20)
Complexitatea timpului Soluția de mai sus este o (n 2/3 ) care este mult mai mic decât O (n).
Putem rezolva problema de mai sus în O (n 1/3 ) timp? Vom discuta despre asta în următoarea postare.
