Trobeu parells de cubs | Set 2 (A n^(1/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
Hem discutit una O ( n 2/3 ) Solució a sota del conjunt 1.
Trobeu parells de cubs | Conjunt 1 (A n^(2/3) Solució)
En aquesta publicació A O ( n 1/3 ) es discuteix la solució.
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 crear una matriu auxiliar de mida n 1/3 . Cada índex I a la matriu emmagatzemarà el valor igual al cub d'aquest índex, és a dir, arr [i] = i^3. Ara el problema es redueix a trobar un parell d’elements en una matriu ordenada la suma de la qual és igual al que es dóna el número n. El problema es discuteix en detall aquí .
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 #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>
Sortida:
(10 27) (19 24)
Complexitat temporal La solució anterior és O (n^(1/3)).
