C++-এ যেসব ট্রিপলেটের যোগফল পারফেক্ট কিউব তাদের গণনা

আমাদের n পূর্ণসংখ্যার একটি অ্যারে দেওয়া আছে এবং আমাদের কাজ হল যেসব ট্রিপলেটের (৩টি মানের সেট) যোগফল পারফেক্ট কিউব তাদের গণনা করা।

পারফেক্ট কিউব কী?

পারফেক্ট কিউব হল এমন একটি সংখ্যা যা যেকোনো সংখ্যার কিউব। যেমন 125 হল 5-এর কিউব, তাই 125 একটি পারফেক্ট কিউব। কিছু পারফেক্ট কিউব পূর্ণসংখ্যা হল: 1, 8, 27, 64, 125...।

সমস্যা অনুযায়ী, অ্যারেতে আমাদের সেই ট্রিপলেট (৩টি মানের সেট) খুঁজে বের করে গণনা করতে হবে যাদের যোগফল একটি পারফেক্ট কিউব সংখ্যার সমান। علاوہ, শর্ত অনুযায়ী ট্রিপলেটের যোগফল সর্বোচ্চ 15000 হতে পারে, তাই কেবল ২৪টি কিউব সম্ভব। আমরা ডাইনামিক প্রোগ্রামিং পদ্ধতি ব্যবহার করব কম জটিলতায় সমস্যা সমাধান করার জন্য।

উদাহরণ

ইনপুট− 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]);
            //-else কারেন্ট স্টেটে +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;
}

// main ফাংশন
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