キューブペアを見つける |セット 1 (n^(2/3) の解)
数値 n が与えられた場合、その数値を 2 つの立方体の合計として表すことができる 2 つのペアを見つけます。言い換えると、与えられた数 n が次のように表現できるような 2 つのペア (a b) と (c d) を見つけます。
n = a^3 + b^3 = c^3 + d^3
ここで、 a b c および d は 4 つの異なる数字です。
例:
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
制約を満たす任意の数値 n は、a b c および d がすべて以下になるような 2 つの異なるペア (a b) および (c d) を持ちます。 n 1/3 。考え方はとてもシンプルです。より小さい数値で形成されるすべての個別のペア (x y) について、 n 1/3 それらの合計 (x 3 +と 3 ) は指定された数値に等しいので、合計をキーとして使用してハッシュ テーブルに格納します。合計が指定された数値に等しいペアが再び現れた場合は、単純に両方のペアを出力します。
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
以下は上記のアイデアの実装です -
// 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)
出力：
(2 24) and (18 20)
時間計算量 上記の解は O(n 2/3 ) これは O(n) よりもはるかに小さいです。
上記の問題を O(n 1/3 ） 時間？それについては次回の投稿で説明します。
