हमें n पूर्णांकों की एक सरणी दी गई है और कार्य उन सभी ट्रिपलेट्स की गिनती करना है जिनका योग एक पूर्ण घन के बराबर है।
पूर्ण घन क्या है
एक पूर्ण घन एक संख्या है जो किसी संख्या का घन है, जैसे 125, 5 का घन है इसलिए हम कह सकते हैं कि 125 एक पूर्ण घन है। कुछ पूर्ण घन पूर्णांक हैं 1, 8, 27, 64, 125...।
तो, समस्या के अनुसार सरणी में हमें उन ट्रिपलेट्स (3 मानों का सेट) को खोजना और गिनना है जिनका योग एक पूर्ण घन संख्या के बराबर है। इसके अलावा प्रदान की गई शर्त के अनुसार ट्रिपलेट का योग अधिकतम 15000 हो सकता है इसलिए केवल 24 घन संभव हैं। इसलिए हम समस्या को कम जटिलता में हल करने के लिए डायनामिक प्रोग्रामिंग दृष्टिकोण का उपयोग करेंगे।
उदाहरण के लिए
इनपुट- array[] = {5, 2, 18, 6, 3}; आउटपुट - ट्रिपलेट्स की संख्या = 1 व्याख्या - 18+6+3 = 27 (एक पूर्ण घन है) इसके अलावा कोई अन्य ट्रिपलेट पूर्ण घन नहीं है। इनपुट - array[] = {1, 2, 3, 4, 5}; आउटपुट - ट्रिपलेट्स की संख्या = 2 व्याख्या - 1 + 2 + 5 = 8 (एक पूर्ण घन है) 1 + 3 + 4 = 8 (एक पूर्ण घन है)
नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण
सकारात्मक पूर्णांकों की सरणी इनपुट करें
इसका आकार गणना करें
डायनामिक प्रोग्रामिंग का उपयोग करके हम सरणी में अंकों की घटना का पता लगाएंगे।
ट्रिपलेट्स की संख्या की गिनती संग्रहीत करने के लिए चर ans को आरंभ करें।
पार करें और ट्रिपलेट के सेट की तीसरी घटना का पता लगाएं और जांचें कि क्या यह एक पूर्ण घन है। यदि ट्रिपलेट एक पूर्ण घन है, तो ans के मान को 1 से बढ़ाएं।
ans लौटाएं।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
int arrd[1001][15001];
// दी गई रेंज में एक संख्या की घटना खोजने के लिए फंक्शन
void compute(int ar[], int num) {
for (int i = 0; i < num; ++i) {
for (int j = 1; j <= 15000; ++j) {
// यदि i == 0
// वर्तमान मान को 1 असाइन करें
if (i == 0)
arrd[i][j] = (j == ar[i]);
// अन्यथा वर्तमान स्थिति में +1 जोड़ें साथ में
// पिछली स्थिति
else
arrd[i][j] = arrd[i - 1][j] + (ar[i] == j);
}
}
}
// उन ट्रिपलेट्स की गिनती करने के लिए फंक्शन जिनका योग
// एक पूर्ण घन है
int countTriplets(int ar[], int num) {
compute(ar, num);
int ans = 0; // उत्तर आरंभ करें
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]);
// j+1 से n तक की रेंज में तीसरे ट्रिपलेट की सभी घटनाओं को गिनें
if (rem > 0)
ans += arrd[num - 1][rem] - arrd[j][rem];
}
}
}
return ans;
}
// मुख्य फंक्शन कोड
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
