পুনরাবৃত্ত বিয়োগ দিয়ে সব উপাদান একই করে অ্যারেতে সর্বোচ্চ যোগফল বের করা C++-তে

মনে করুন আমাদের n উপাদানের একটি অ্যারে আছে। সব উপাদান একই করে অ্যারেতে সর্বোচ্চ সম্ভাব্য যোগফল বের করতে হবে। একমাত্র অপারেশন যা অনুমোদিত হল যেকোনো দুটি উপাদান বেছে নেওয়া এবং তাদের মধ্যে বড়টিকে তাদের निरপেক্ষ পার্থক্যে রিপ্লেস করা। মনে করুন উপাদানগুলো হল [9, 12, 3, 6]। তবে আউটপুট হবে 12। প্রথমে A[1] কে A[1] - A[3] = 12 - 6 = 6 দিয়ে রিপ্লেস করুন। এখন উপাদানগুলো [9, 6, 3, 6], তারপর A[3] কে A[3] - A[2] = 6 - 3 = 3 দিয়ে রিপ্লেস করুন। উপাদানগুলো [9, 6, 3, 3]। তারপর A[0] কে A[0] - A[1] = 9 - 6 = 3 দিয়ে রিপ্লেস করুন। উপাদানগুলো [3, 6, 3, 3]। এবং সর্বশেষে A[1] কে A[1] - A[3] = 6 - 3 = 3 দিয়ে রিপ্লেস করুন। উপাদানগুলো [3, 3, 3, 3]। তাই সব একই। এবং যোগফল ১২

যদি অপারেশনটি বিশ্লেষণ করি, তবে এটি হবে A[i] = A[i] - A[j], যেখানে A[i] > A[j]। তাই আমরা দুটি সংখ্যা নিব, তারপর বড় মানটি তাদের निरপেক্ষ পার্থক্যে রিপ্লেস করব। এই ধাপগুলো পুনরাবৃত্ত করব যতক্ষণ না সব একই হয়।

উদাহরণ

#include <iostream>
#include <algorithm>
using namespace std;

int findSameElement(int arr[], int n) {
    int gcd_val = arr[0];
    for (int i = 1; i < n; i++)
        gcd_val = __gcd(arr[i], gcd_val);
    return gcd_val;
}

int getMaxSum(int arr[], int n) {
    int value = findSameElement(arr, n);
    return (value * n);
}

int main() {
    int arr[] = {3, 9, 6, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "The maximum sum is: " << getMaxSum(arr, n);
}

আউটপুট

The maximum sum is: 12