এই সমস্যাতে, আমাদের একটি অ্যারে arr[] দেওয়া আছে যার আকার n এবং একটি পূর্ণসংখ্যা k। আমাদের কাজ হলো i থেকে j ইনডেক্স পর্যন্ত সাবঅ্যারে খুঁজে বের করা এবং তার সব এলিমেন্টের বিটওয়াইজ AND কম্পিউট করা। এরপর abs(K- (সাবঅ্যারের বিটওয়াইজ AND))-এর মিনিমাম মান প্রিন্ট করা।
উদাহরণ দিয়ে বুঝি,
ইনপুট − arr[] = {5, 1}, k = 2
আউটপুট −
সমস্যা সমাধানের কিছু পদ্ধতি হতে পারে।
একটি সহজ সমাধান হচ্ছে ডায়রেক্ট মেথড। সব সাব-অ্যারেের বিটওয়াইজ AND বের করে |K-X| বের করা।
স্টেপ ১ − সব সাব-অ্যারেের বিটওয়াইজ AND বের করুন।
স্টেপ ২ − উপরের স্টেপ ১ থেকে পাওয়া প্রতিটি মান (ধরি X) এর জন্য |k - X|-এর মান বের করুন।
স্টেপ ৩ − উপরে পাওয়া মিনিমাম মান একটি min ভেরিয়েবলে সংরক্ষণ করুন।
স্টেপ ৪ − শেষে min প্রিন্ট করুন।
উদাহরণ
আমাদের সমাধানের ওয়ার্কিং ইলাস্ট্রেট করার প্রোগ্রাম,
#include <iostream>
using namespace std;
int CalcBitwiseANDClosestK(int arr[], int n, int k){
int minimum = 1000;
for (int i = 0; i < n; i++) {
int X = arr[i];
for (int j = i; j < n; j++) {
X &= arr[j];
minimum = min(minimum, abs(k - X));
}
}
return minimum;
}
int main() {
int arr[] = { 1, 6 , 4, 9, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 5;
cout<<"Minimum value difference between Bitwise AND of sub-array and K is "<<CalcBitwiseANDClosestK(arr, n, k);
return 0;
}আউটপুট
Minimum value difference between Bitwise AND of sub-array and K is 1
আরেকটি সমাধান হচ্ছে সাব-অ্যারেতে AND অপারেশনের বৈশিষ্ট্য পর্যবেক্ষণ করা। বিটওয়াইজ AND-এর একটি বৈশিষ্ট্য আছে যে এটি কখনো বড় হয় না। তাই আমাদেরকে মিনিমাম পার্থক্যের ऊपर নজর রাখতে হবে যা X ≤ K হলে বড়তে থাকবে।
উদাহরণ
#include <iostream>
using namespace std;
int CalcBitwiseANDClosestK(int arr[], int n, int k){
int minimum = 1000000;
for (int i = 0; i < n; i++) {
int BitwiseAND = arr[i];
for (int j = i; j < n; j++) {
BitwiseAND &= arr[j];
minimum = min(minimum, abs(k - BitwiseAND));
if (BitwiseAND <= k)
break;
}
}
return minimum;
}
int main() {
int arr[] = {1, 6 , 4, 9, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 5;
cout<<"Minimum value difference between Bitwise AND of sub-array and K is "<<CalcBitwiseANDClosestK(arr, n, k);
return 0;
}আউটপুট
Minimum value difference between Bitwise AND of sub-array and K is 1
