查找立方体对|集2（n^（1/3）解）-yiteyi-C++库

给定一个数n，找到两对可以表示为两个立方体之和的数。换句话说，找到两对（a，b）和（c，d），这样给定的数字n可以表示为

null

n = a^3 + b^3 = c^3 + d^3

其中a、b、c和d是四个不同的数字。 例如：

Input: n = 1729Output: (1, 12) and (9, 10)Explanation: 1729 = 1^3 + 12^3 = 9^3 + 10^3Input: n = 4104Output: (2, 16) and (9, 15)Explanation: 4104 = 2^3 + 16^3 = 9^3 + 15^3Input: n = 13832Output: (2, 24) and (18, 20)Explanation: 13832 = 2^3 + 24^3 = 18^3 + 20^3

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

我们讨论了一个O( N ^2/3 )解决方案在下面的集合1中。查找立方体对|集1（n^（2/3）解决方案）在这篇文章中，一个O( N ^1/3 )讨论了解决方案。满足约束的任何数字n都将有两个不同的对（a，b）和（c，d），使得a，b，c和d都小于 N ^1/3 .这个想法是创建一个大小的辅助数组 N ^1/3 .数组中的每个索引i将存储与该索引的立方相等的值，即arr[i]=i^3。现在问题归结为在一个排序数组中寻找一对元素，其和等于给定的数n。这个问题将被详细讨论在这里 . 以下是上述理念的实施：

C++

                         // C++ program to find pairs that can represent                       
                         // the given number as sum of two cubes                       
                         #include <iostream>                       
                         #include <cmath>                       
                         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                       
                         // 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                                     ""                                     ;                       
                                                 $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 +                       
                                                 ")<br>"                                     );                       
                                                 l++; r--;                       
                                                 }                       
                                                 }                       
                         }                       
           
                         // Driver Code                       
                         var                                     n = 20683;                       
                         findPairs(n);                       
           
           
                         // This code is contributed by Amit Katiyar                       
           
                         </script>                       

输出：

(10, 27)(19, 24)

时间复杂性 上述溶液的浓度为O（n^（1/3））。本文由 阿迪蒂亚·戈尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章