Poiščite pare kocke | Set 1 (a n^(2/3) rešitev)
Glede na številko n poiščite dva para, ki lahko predstavljata številko kot vsoto dveh kock. Z drugimi besedami, poiščite dva para (a b) in (c d), tako da je mogoče dati številki n izraziti kot
n = a^3 + b^3 = c^3 + d^3
kjer sta B C in D štiri različne številke.
Primeri:
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
Poljubno število n, ki izpolnjuje omejitev n 1/3 . Ideja je zelo preprosta. Za vsak različen par (x y), ki ga tvorijo številke manj kot n 1/3 Če njihova vsota (x 3 + in 3 ) je enako dani številki, ki jih shranimo v hash tabelo z uporabo vsote kot ključa. Če se pari z vsoto, ki je enaka določeni številki, spet natisnemo oba para.
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
Spodaj je izvedba zgornje ideje -
// 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)
Izhod:
(2 24) and (18 20)
Časovna zapletenost zgornje raztopine je o (n 2/3 ) kar je veliko manj kot O (n).
Ali lahko zgornjo težavo rešimo v O (n 1/3 ) Čas? O tem bomo razpravljali v naslednji objavi.
