এখানে অ্যারে সংক্রান্ত একটি আকর্ষণীয় সমস্যা দেখব। n উপাদান বিশিষ্ট একটি অ্যারে দেওয়া আছে। আমাদের আরেকটি n আকারের অ্যারে তৈরি করতে হবে, যেখানে i-তম পজিশনে প্রথম অ্যারের সব উপাদানের গুণফল থাকবে i-তম উপাদান বাদ দিয়ে। সীমাবদ্ধতা: ভাগ অপারেটর (division operator) ব্যবহার করা যাবে না।
যদি ভাগ ব্যবহার করা যেত, তবে সব উপাদানের গুণফল বের করে i-তম উপাদান দিয়ে ভাগ করে ফলাফল অ্যারেতে রাখলেই হত।
এখানে আমরা দুটি আলাদা অ্যারে তৈরি করব: left এবং right। left[i] তে arr[i]-র বামপাশের সব উপাদানের গুণফল থাকবে (arr[i] বাদ দিয়ে), আর right[i] তে ডানপাশের সব উপাদানের গুণফল থাকবে (arr[i] বাদ দিয়ে)। এই সমাধান O(n) সময় নেয় কিন্তু অতিরিক্ত স্পেস লাগে।
অ্যালগরিদম
productArray(arr, n)
শুরু
left এবং right নামক দুটি n আকারের অ্যারে সংজ্ঞায়িত করুন
res নামক n আকারের অ্যারে সংজ্ঞায়িত করুন
left[0] এবং right[n-1] কে ১ সেট করুন
i := 1 থেকে n-1 পর্যন্ত, করুন
left[i] = left[i-1] * arr[i-1]
শেষ করুন
i := n-2 থেকে 0 পর্যন্ত, করুন
right[i] = right[i+1] * arr[i+1]
শেষ করুন
i := 0 থেকে n-1 পর্যন্ত, করুন
res[i] = left[i] * right[i]
শেষ করুন
res ফেরত দিন
শেষ
উদাহরণ কোড
#include <iostream>
using namespace std;
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
void productArray(int arr[], int product[], int n) {
// left এবং right অ্যারে তৈরি
int *left = new int[n];
int *right = new int[n];
// left[0] এবং right[n-1] কে ১ সেট করুন
left[0] = right[n-1] = 1;
for (int i = 1; i < n; i++) {
left[i] = left[i-1] * arr[i-1];
}
for (int i = n-2; i >= 0; i--) {
right[i] = right[i+1] * arr[i+1];
}
// left এবং right ব্যবহার করে গুণফল অ্যারে বের করুন
for (int i = 0; i < n; i++) {
product[i] = left[i] * right[i];
}
}
int main() {
int myArr[7] = {5, 4, 7, 6, 9, 2, 3};
int resArr[7];
cout << "Initial Array: ";
printArray(myArr, 7);
productArray(myArr, resArr, 7);
cout << "Final Array: ";
printArray(resArr, 7);
return 0;
}
আউটপুট
Initial Array: 5 4 7 6 9 2 3 Final Array: 9072 11340 6480 7560 5040 22680 15120
