এখানে আমরা একটি আকর্ষণীয় সমস্যা দেখব। ধরা যাক n আকারের একটি বাইনারি অ্যারে দেওয়া আছে। এখানে n > 3। ১ বা true মান সক্রিয় অবস্থা নির্দেশ করে এবং ০ বা false নিষ্ক্রিয়। আরেকটি সংখ্যা k ও দেওয়া আছে। k দিন পর সক্রিয় বা নিষ্ক্রিয় সেলগুলো খুঁজে বের করতে হবে। প্রতিদিন i-তম সেল সক্রিয় হবে যদি এর বাম ও ডান সেল এক না হয়, যদি এক হয় তবে নিষ্ক্রিয় হবে। সবচেয়ে বাম ও ডান সেলের কোনো পূর্ববর্তী বা পরবর্তী সেল নেই। তাই বাম ও ডান সেল সবসময় ০ থাকবে।
একটি উদাহরণ দেখি। ধরা যাক অ্যারে = {0, 1, 0, 1, 0, 1, 0, 1}, এবং k = 3। দিন दर দিন কীভাবে পরিবর্তন হচ্ছে তা দেখি।
- ১ দিন পর অ্যারে হবে {1, 0, 0, 0, 0, 0, 0, 0}
- ২ দিন পর অ্যারে হবে {0, 1, 0, 0, 0, 0, 0, 0}
- ৩ দিন পর অ্যারে হবে {1, 0, 1, 0, 0, 0, 0, 0}
সুতরাং ২টি সক্রিয় এবং ৬টি নিষ্ক্রিয় সেল
অ্যালগরিদম
activeCellKdays(arr, n, k)
begin make a copy of arr into temp for i in range 1 to k, do temp[0] := 0 XOR arr[1] temp[n-1] := 0 XOR arr[n-2] for each cell i from 1 to n-2, do temp[i] := arr[i-1] XOR arr[i+1] done copy temp to arr for next iteration done count number of 1s as active, and number of 0s as inactive, then return the values. end
উদাহরণ
#include <iostream> using namespace std; void activeCellKdays(bool arr[], int n, int k) { bool temp[n]; //temp holds the copy of the arr for (int i=0; i<n ; i++) temp[i] = arr[i]; for(int i = 0; i<k; i++){ temp[0] = 0^arr[1]; //set value for left cell temp[n-1] = 0^arr[n-2]; //set value for right cell for (int i=1; i<=n-2; i++) //for all intermediate cell if left and right are not same, put 1 temp[i] = arr[i-1] ^ arr[i+1]; for (int i=0; i<n; i++) arr[i] = temp[i]; //copy back the temp to arr for the next iteration } int active = 0, inactive = 0; for (int i=0; i<n; i++) if (arr[i]) active++; else inactive++; cout << "Active Cells = "<< active <<", Inactive Cells = " << inactive; } main() { bool arr[] = {0, 1, 0, 1, 0, 1, 0, 1}; int k = 3; int n = sizeof(arr)/sizeof(arr[0]); activeCellKdays(arr, n, k); }আউটপুট
Active Cells = 2, Inactive Cells = 6
