C++ এ একটি পণ্য অ্যারে ধাঁধা?

এখানে আমরা অ্যারে সম্পর্কিত একটি আকর্ষণীয় সমস্যা দেখতে পাব। n উপাদান সহ একটি অ্যারে আছে. আমাদের n উপাদানের আরেকটি অ্যারে তৈরি করতে হবে। কিন্তু দ্বিতীয় অ্যারের i-th অবস্থানটি i-th উপাদান ছাড়া প্রথম অ্যারের সমস্ত উপাদানের গুণফলকে ধরে রাখবে। এবং একটি সীমাবদ্ধতা হল এই সমস্যাটিতে আমরা বিভাগ অপারেটর ব্যবহার করতে পারি না।

যদি আমরা বিভাগ, অপারেশন ব্যবহার করতে পারি, তাহলে আমরা সহজেই এই সমস্যাটি সমাধান করতে পারি, সমস্ত উপাদানের গুণফল পেয়ে, তারপর প্রথম অ্যারের i-th উপাদানকে ভাগ করে দ্বিতীয় অ্যারের i-th স্থানে সংরক্ষণ করি।

এখানে আমরা দুটি পৃথক অ্যারে তৈরি করে এটি সমাধান করছি। বাম এবং ডান বাম[i] অ্যারে[i] ব্যতীত অ্যারে[i] এর বামে সমস্ত উপাদানের গুণফল ধরে রাখবে, এবং ডান[i] arr[i] ব্যতীত arr[i] এর ডানদিকে সমস্ত উপাদানের গুণফল ধরে রাখবে। এই সমাধানটি O(n) সময় নেবে। তবে এটি অতিরিক্ত স্থান নেবে৷

অ্যালগরিদম

productArray(arr, n)

begin
   define two arrays left and right of size n
   define an array called res of size n
   the first element of left and last element of right is set as 1
   for i in range 1 to n, do
      left[i] = left[i-1] * arr[i-1]
   done
   for i in range n-1 down to 1, do
      right[i] = right[i+1] * arr[i+1]
   done
   for i in range 1 to n, do
      res[i] = left[i] * right[i];
   done
   return res
end

উদাহরণ

#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) {
   //create left right array
   int *left = new int[sizeof(int)*n];
   int *right = new int[sizeof(int)*n];
   //set the first element of left[] and last element of right[] as 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];
   }
   //get product array using left and right array
   for(int i = 0; i<n; i++) {
      product[i] = left[i] * right[i];
   }
}
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);
}

আউটপুট

Initial Array: 5 4 7 6 9 2 3
Final Array: 9072 11340 6480 7560 5040 22680 15120