আমাদের 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) নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি
-
ধনাত্মক পূর্ণসংখ্যার অ্যারে ইনপুট করুন
-
এর আকার গণনা করুন
-
ডায়নামিক প্রোগ্রামিং ব্যবহার করে আমরা অ্যারেতে সংখ্যার উপস্থিতি খুঁজে পাব।
-
ট্রিপলেটের সংখ্যা সংরক্ষন করতে ভেরিয়েবল উত্তর শুরু করুন।
-
অতিক্রম করুন এবং ট্রিপলেট সেটের তৃতীয় ঘটনাটি খুঁজুন এবং এটি একটি নিখুঁত ঘনক কিনা তা সন্ধান করুন। যদি ট্রিপলেট একটি নিখুঁত ঘনক হয়, তাহলে উত্তরের মান 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
