हमें 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 को इनिशियलाइज़ करें।
-
पार करें और त्रिक के समुच्चय का तीसरा अवसर ज्ञात करें और ज्ञात करें कि क्या यह एक पूर्ण घन है। यदि त्रिक एक पूर्ण घन है, तो 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