C++ সম অ্যারে পাজল (Sum Array Puzzle)

অ্যারে (Array) একই ডেটা টাইপের একাধিক উপাদান স্টোর করে। দৈর্ঘ্য পূর্বে ফিক্স করতে হয়।

সম অ্যারে পাজল-এ একটি অ্যারে A1 দেওয়া থাকে। আমরা একটি নতুন অ্যারে S1 তৈরি করব যেখানে S1[i] = A1-এর সব উপাদানের যোগফল ছাড়া A1[i]।

উদাহরণ

Array A1 = {1,2,3,4,6} Output S1 = {15,14,13,12,10}

ব্যাখ্যা

• Sum[0] = 2+3+4+6 = 15 (0th ইনডেক্স বাদ)
• Sum[1] = 1+3+4+6 = 14
• Sum[2] = 1+2+4+6 = 13
• Sum[3] = 1+2+3+6 = 12
• Sum[4] = 1+2+3+4 = 10

অ্যালগরিদম

1. সম অ্যারে sum[n] শূন্য দিয়ে ইনিশিয়ালাইজ করুন।
2. প্রতিটি i এর জন্য, j = 0 to n-1 লুপ চালান।
3. যদি i != j হয়, তবে sum[i] += arr[j]।
4. সম অ্যারে প্রিন্ট করুন।

অপ্টিমাইজড পদ্ধতিতে leftSum এবং rightSum ব্যবহার করে O(n) টাইমে করা যায়।

C++ কোড উদাহরণ (অপ্টিমাইজড)

#include <iostream>
using namespace std;

int main() {
    int arr[] = {3, 6, 4, 8, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    int leftSum[n], rightSum[n], Sum[n];
    leftSum[0] = 0;
    rightSum[n - 1] = 0;
    cout << "The original array is : \n";
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    for (int i = 1; i < n; i++)
        leftSum[i] = arr[i - 1] + leftSum[i - 1];
    for (int j = n - 2; j >= 0; j--)
        rightSum[j] = arr[j + 1] + rightSum[j + 1];
    for (int i = 0; i < n; i++)
        Sum[i] = leftSum[i] + rightSum[i];
    cout << "\nThe sum array is : \n";
    for (int i = 0; i < n; i++)
        cout << Sum[i] << " ";
    return 0;
}

আউটপুট

The original array is : 3 6 4 8 9
The sum array is : 27 24 26 22 21