ধারণা
প্রদত্ত দুটি পূর্ণসংখ্যা N এবং K এর সাপেক্ষে, আমাদের কাজ হল N স্বতন্ত্র পূর্ণসংখ্যা নির্ণয় করা যার বিটওয়াইজ বা K এর সমান। দেখা গেছে যদি কোনো সম্ভাব্য উত্তর না থাকে তাহলে প্রিন্ট করুন -1।
ইনপুট
N = 4, K = 6
আউটপুট
6 0 1 2
ইনপুট
N = 11, K = 6
আউটপুট
-1
এর কোনো সমাধান পাওয়া সম্ভব নয়।
পদ্ধতি
-
আমাদের জানা আছে যে সংখ্যার ক্রমটির বিট-ওয়াইজ OR যদি K হয় তাহলে K তে 0 থাকা সমস্ত বিট ইনডেক্সগুলিকেও সমস্ত সংখ্যায় শূন্য হতে হবে৷
-
এর ফলস্বরূপ, আমাদের শুধুমাত্র সেই অবস্থানগুলি পরিবর্তন করতে হবে যেখানে K-তে বিট 1 হয়। গণনাটি Bit_K হয়।
-
বর্তমানে, আমরা Bit_K বিট দিয়ে pow(2, Bit_K) স্বতন্ত্র সংখ্যা তৈরি করতে পারি। এর ফলস্বরূপ, যদি আমরা একটি সংখ্যাকে K হিসাবে গণ্য করি, তবে অবশিষ্ট N – 1 সংখ্যাগুলি K-এ 0 এবং অন্যান্য বিট অবস্থানের জন্য প্রতিটি সংখ্যার সমস্ত বিট 0 সেট করে তৈরি করা যেতে পারে যা Bit_K বিট ব্যতীত অন্যান্য স্থানান্তর। সংখ্যা K.
-
এটা দেখা গেছে যদি pow(2, Bit_K)
উদাহরণ
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define MAX1 32
ll pow2[MAX1];
bool visited1[MAX1];
vector<int> ans1;
// Shows function to pre-calculate
// all the powers of 2 upto MAX
void power_2(){
ll ans1 = 1;
for (int i = 0; i < MAX1; i++) {
pow2[i] = ans1;
ans1 *= 2;
}
}
// Shows function to return the
// count of set bits in x
int countSetBits(ll x1){
// Used to store the count
// of set bits
int setBits1 = 0;
while (x1 != 0) {
x1 = x1 & (x1 - 1);
setBits1++;
}
return setBits1;
}
// Shows function to add num to the answer
// by placing all bit positions as 0
// which are also 0 in K
void add(ll num1){
int point1 = 0;
ll value1 = 0;
for (ll i = 0; i < MAX1; i++) {
// Bit i is 0 in K
if (visited1[i])
continue;
else {
if (num1 & 1) {
value1 += (1 << i);
}
num1 /= 2;
}
}
ans1.push_back(value1);
}
// Shows function to find and print N distinct
// numbers whose bitwise OR is K
void solve(ll n1, ll k1){
// Choosing K itself as one number
ans1.push_back(k1);
// Find the count of set bits in K
int countk1 = countSetBits(k1);
// It is not possible to get N
// distinct integers
if (pow2[countk1] < n1) {
cout << -1;
return;
}
int count1 = 0;
for (ll i = 0; i < pow2[countk1] - 1; i++) {
// Add i to the answer after
// placing all the bits as 0
// which are 0 in K
add(i);
count1++;
// Now if N distinct numbers are generated
if (count1 == n1)
break;
}
// Now print the generated numbers
for (int i = 0; i < n1; i++) {
cout << ans1[i] << " ";
}
}
// Driver code
int main(){
ll n1 = 4, k1 = 6;
// Pre-calculate all
// the powers of 2
power_2();
solve(n1, k1);
return 0;
} আউটপুট
6 0 1 2
