合計がC++の完全な立方体に等しいすべてのトリプレットを数えます

n個の整数の配列が与えられ、タスクは、合計が完全な立方体に等しいすべてのトリプレットの数を計算することです。

完璧な立方体とは

完全な立方体は、任意の数の立方体である数です。たとえば、125は5の立方体であるため、125は完全な立方体であると言えます。完全な立方整数のいくつかは、1、8、27、64、125…です。

したがって、配列の問題に応じて、合計が完全な立方数に等しいトリプレット（3つの値のセット）を見つけてカウントする必要があります。さらに、トリプレットの合計が最大15000であるという条件で、24個のキューブしか存在できません。そのため、動的計画法を使用して、問題をより簡単に解決します。

例

Input− array[] = { 5, 2, 18, 6, 3 };
Output − Number of Triplets are= 1
Explanation − 18+6+3 = 27 (is a perfect cube)
Except this no other triplet is a perfect cube.

Input − array[] = {1, 2, 3, 4, 5};
Output − Number of Triplets are= 2
Explanation − 1 + 2 + 5 = 8 (is a perfect cube)
1 + 3 + 4 = 8 (is a perfect cube)

以下のプログラムで使用されているアプローチは次のとおりです

• 正の整数の配列を入力します

• サイズを計算する

• 動的計画法を使用して、配列内の数字の出現を検出します。

• 変数ansを初期化して、トリプレット数のカウントを格納します。

• トリプレットセットの3番目の出現をトラバースして見つけ、それが完全な立方体であるかどうかを見つけます。トリプレットが完全な立方体である場合は、ansの値を1ずつ増やします。

• 回答を返します。

例

#include <bits/stdc++.h>
using namespace std;
int arrd[1001][15001];
// Function to find the occurence of a number
// in the given range
void compute(int ar[], int num){
   for (int i = 0; i < num; ++i) {
      for (int j = 1; j <= 15000; ++j) {
         // if i == 0
         // assign 1 to present value
         if (i == 0)
         arrd[i][j] = (j == ar[i]);
         // else add +1 to current state with
         // previous state
         else
         arrd[i][j] = arrd[i - 1][j] + (ar[i] == j);
      }
   }
}
// Function to count the triplets whose sum
// is a perfect cube
int countTriplets(int ar[], int num){
   compute(ar, num);
   int ans = 0; // Initialize answer
   for (int i = 0; i < num - 2; ++i) {
      for (int j = i + 1; j < num - 1; ++j) {
         for (int k = 1; k <= 24; ++k) {
            int cube = k * k * k;
            int rem = cube - (ar[i] + ar[j]);
            // count all occurrence of third triplet
            // in range from j+1 to n
            if (rem > 0)
            ans += arrd[num - 1][rem] - arrd[j][rem];
         }
      }
   }
   return ans;
}
// main function code
int main(){
   int ar[] = { 5, 2, 18, 6, 3 };
   int num = sizeof(ar) / sizeof(ar[0]);
   cout << “Number of Triplets are= ”<<countTriplets(ar, num);
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます-

Number of Triplets are= 1