Găsiți perechi de cuburi | Set 2 (A n^(1/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
Am discutat despre o O ( n 2/3 ) Soluție în setul de mai jos 1.
Găsiți perechi de cuburi | Set 1 (a n^(2/3) soluție)
În acest post a o ( n 1/3 ) soluția este discutată.
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 de a crea un tablou auxiliar de dimensiuni n 1/3 . Fiecare index I din tablou va stoca valoarea egală cu cubul acelui index, adică arr [i] = i^3. Acum problema se reduce la găsirea unei perechi de elemente într -un tablou sortat a cărui sumă este egală cu numărul dat n. Problema este discutată în detaliu Aici .
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 #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 a array of size of size 'cubeRoot' int cube [ cubeRoot + 1 ]; // for index i cube[i] will contain i^3 for ( int i = 1 ; i <= cubeRoot ; i ++ ) cube [ i ] = i * i * i ; // Find all pairs in above sorted // array cube[] whose sum is equal to n int l = 1 ; int r = cubeRoot ; while ( l < r ) { if ( cube [ l ] + cube [ r ] < n ) l ++ ; else if ( cube [ l ] + cube [ r ] > n ) r -- ; else { cout < < '(' < < l < < ' ' < < r < < ')' < < endl ; l ++ ; r -- ; } } } // Driver function int main () { int n = 20683 ; findPairs ( n ); return 0 ; }
Java // Java program to find pairs // that can represent the given // number as sum of two cubes import java.io.* ; class GFG { // 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 a array of // size of size 'cubeRoot' int cube [] = new int [ cubeRoot + 1 ] ; // for index i cube[i] // will contain i^3 for ( int i = 1 ; i <= cubeRoot ; i ++ ) cube [ i ] = i * i * i ; // Find all pairs in above // sorted array cube[] // whose sum is equal to n int l = 1 ; int r = cubeRoot ; while ( l < r ) { if ( cube [ l ] + cube [ r ] < n ) l ++ ; else if ( cube [ l ] + cube [ r ] > n ) r -- ; else { System . out . println ( '(' + l + ' ' + r + ')' ); l ++ ; r -- ; } } } // Driver Code public static void main ( String [] args ) { int n = 20683 ; findPairs ( n ); } } // This code is contributed by anuj_67.
Python3 # Python3 program to find pairs that # can represent the given number # as sum of two cubes import math # Function to find pairs that can # represent the given number as # sum of two cubes def findPairs ( n ): # find cube root of n cubeRoot = int ( math . pow ( n 1.0 / 3.0 )); # create a array of # size of size 'cubeRoot' cube = [ 0 ] * ( cubeRoot + 1 ); # for index i cube[i] # will contain i^3 for i in range ( 1 cubeRoot + 1 ): cube [ i ] = i * i * i ; # Find all pairs in above sorted # array cube[] whose sum # is equal to n l = 1 ; r = cubeRoot ; while ( l < r ): if ( cube [ l ] + cube [ r ] < n ): l += 1 ; else if ( cube [ l ] + cube [ r ] > n ): r -= 1 ; else : print ( '(' l ' ' math . floor ( r ) ')' end = '' ); print (); l += 1 ; r -= 1 ; # Driver code n = 20683 ; findPairs ( n ); # This code is contributed by mits
C# // C# program to find pairs // that can represent the given // number as sum of two cubes using System ; class GFG { // 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 a array of // size of size 'cubeRoot' int [] cube = new int [ cubeRoot + 1 ]; // for index i cube[i] // will contain i^3 for ( int i = 1 ; i <= cubeRoot ; i ++ ) cube [ i ] = i * i * i ; // Find all pairs in above // sorted array cube[] // whose sum is equal to n int l = 1 ; int r = cubeRoot ; while ( l < r ) { if ( cube [ l ] + cube [ r ] < n ) l ++ ; else if ( cube [ l ] + cube [ r ] > n ) r -- ; else { Console . WriteLine ( '(' + l + ' ' + r + ')' ); l ++ ; r -- ; } } } // Driver Code public static void Main () { int n = 20683 ; findPairs ( n ); } } // This code is contributed by anuj_67.
PHP // PHP 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 $cubeRoot = pow ( $n 1.0 / 3.0 ); // create a array of // size of size 'cubeRoot' $cube = array (); // for index i cube[i] // will contain i^3 for ( $i = 1 ; $i <= $cubeRoot ; $i ++ ) $cube [ $i ] = $i * $i * $i ; // Find all pairs in above sorted // array cube[] whose sum // is equal to n $l = 1 ; $r = $cubeRoot ; while ( $l < $r ) { if ( $cube [ $l ] + $cube [ $r ] < $n ) $l ++ ; else if ( $cube [ $l ] + $cube [ $r ] > $n ) $r -- ; else { echo '(' $l ' ' floor ( $r ) ')' ; echo ' n ' ; $l ++ ; $r -- ; } } } // Driver code $n = 20683 ; findPairs ( $n ); // This code is contributed by anuj_67. ?>
JavaScript < script > // 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 var cubeRoot = parseInt ( Math . pow ( n 1.0 / 3.0 )); // create a array of // size of size 'cubeRoot' var cube = Array . from ({ length : cubeRoot + 1 } ( _ i ) => 0 ); // for index i cube[i] // will contain i^3 for ( i = 1 ; i <= cubeRoot ; i ++ ) cube [ i ] = i * i * i ; // Find all pairs in above // sorted array cube // whose sum is equal to n var l = 1 ; var r = cubeRoot ; while ( l < r ) { if ( cube [ l ] + cube [ r ] < n ) l ++ ; else if ( cube [ l ] + cube [ r ] > n ) r -- ; else { document . write ( '(' + l + ' ' + r + ')
' ); l ++ ; r -- ; } } } // Driver Code var n = 20683 ; findPairs ( n ); // This code is contributed by Amit Katiyar < /script>
Ieșire:
(10 27) (19 24)
Complexitatea timpului Soluția de mai sus este O (n^(1/3)).
