medium-level-bit.cpp

// // 🔹 XOR Based Problems ⭐⭐⭐
// // Find two unique numbers
// // Missing number
// // XOR from 1 to N
// // Find duplicate using XOR
// // 🔹 Bit Counting & Tricks
// // Brian Kernighan’s Algorithm ⭐⭐⭐
// // Count bits efficiently
// // Count bits from 1 to N
// // 🔹 Subsets & Bitmasking ⭐⭐⭐
// // Generate all subsets (bitmask)
// // Iterate over subsets
// // Subset sum using bitmask
// // 🔹 Range & Logic Problems
// // Bitwise AND of range
// // Maximum XOR of two numbers ⭐⭐⭐
// // Minimum XOR pair
// // 🔹 Practical Use Cases
// // Swap two numbers using XOR
// // Check if two numbers differ by one bit

// // 👉 Goal: Use bit manipulation in real problems




// // 🔹 XOR BASED PROBLEMS ⭐⭐⭐
// // 1. Find Two Unique Numbers
// // 💡 Problem

// // All numbers appear twice except 2 numbers

// // 📐 Idea
// // a ^ a = 0  
// // 0 ^ x = x
// // So XOR of all gives a ^ b (the two unique numbers)
// // To separate a and b, find a set bit in a ^ b
// // Use that bit to divide numbers into two groups
// // Each group will have one unique number
// // Use XOR:

// // xor = a ^ b (two unique numbers)
// // Find a set bit to separate them
// // ⚙️ Approach
// // XOR all → get a ^ b
// // Find rightmost set bit
// // Divide numbers into 2 groups





#include<bits/stdc++.h>
using namespace std;
pair<int,int>findTwoUnique(vector<int>&arr){
    int Xr=0;
    for(int x:arr){
        Xr^=x;
    }
    int set_bit=Xr&(-Xr);
    int a=0,b=0;
    for(int x:arr){
        if(x&set_bit){
            a^=x;
        }
        else{
            b^=x;
        }
    }
    return {a,b};
}
int main(){
    int n;
    cin>>n;
    vector<int>arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    pair<int,int>res=findTwoUnique(arr);
    cout<<"Two unique numbers are: "<<res.first<<" and "<<res.second<<endl;//output two unique numbers if arr is given as input arr=[1,2,3,2,1,4] and n is 6 => output is 3 and 4
}



// // 2. Missing Number
// // 💡 Problem
// // Array contains numbers from 0 to N, one missing
// // 📐 Idea
// // 0 ^ 1 ^ 2 ^ ... ^ N ^ arr elements
// // Missing number will be the result
// // ⚙️ Approach
// // XOR all numbers from 0 to N and all array elements
// // Result is the missing number
// //array input: arr=[3,0,1] and n is 3 => output is 2 (missing number is 2)
// //if array input is arr=[0,1,3,4] and n is 4 => output is 2 (missing number is 2)
// //if array input is arr=[1,2,3] and n is 3 => output is 0 (missing number is 0)
// //if array input is arr=[1,2,4] and n is 4 => output is 3 (missing number is 3)



#include<bits/stdc++.h>
using namespace std;
int missingNumber(vector<int>& arr){
    int n=arr.size();
    int Xr=0;
    for(int i=0;i<=n;i++){
        Xr^=i;       
    }
    for(int x:arr){
        Xr^=x;
    }
    return Xr;
}
int main(){
    int n;
    cin>>n;
    vector<int>arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    cout<<"Missing number is: "<<missingNumber(arr)<<endl;//output missing number if arr is given as input arr=[3,0,1] and n is 3 => output is 2
    return 0;
}




// // 3. XOR from 1 to N
// // 📐 Pattern
// // n % 4 == 0 → n
// // n % 4 == 1 → 1
// // n % 4 == 2 → n+1
// // n % 4 == 3 → 0
// // 💡 Idea
// // XOR from 1 to N follows a pattern based on n mod 4
// // ⚙️ Approach
// // Use the pattern to compute XOR from 1 to N in O(1) time
// // XOR from 1 to N can be computed using the following pattern:
// // If n % 4 == 0, then XOR is n
// // If n % 4 == 1, then XOR is 1
// // If n % 4 == 2, then XOR is n+1
// // If n % 4 == 3, then XOR is 0



#include<bits/stdc++.h>
using namespace std;
int xorFrom1ToN(int n){
    if(n%4==0) return n;
    else if(n%4==1) return 1;
    else if(n%4==2) return n+1;
    else return 0;
}
int main(){
    int n;
    cin>>n;
    cout<<"XOR from 1 to "<<n<<" is: "<<xorFrom1ToN(n)<<endl;//output XOR from 1 to n if n is given as input n=5 => output is 1 (XOR is 1^2^3^4^5 = 1)
    return 0;
}




// // 4. Find Duplicate using XOR
// // 💡 Problem
// // Numbers from 1 to N, one duplicate

// // ⚙️ Approach
// // XOR all numbers from 1 to N and all array elements
// // Result is the duplicate number
// // XOR array + XOR 1..N
// //if there is one duplicate, it will be the result
// // If there are multiple duplicates, we can keep track of counts and XOR only those with count




#include<bits/stdc++.h>
using namespace std;
int findDuplicate(vector<int>&arr){
    int n=arr.size();
    int Xr=0;
    for(int i=1;i<=n-1;i++){
        Xr^=i;
    }
    for(int x:arr){
        Xr^=x;
    }
    return Xr;
}
int main(){
    int n;
    cin>>n;
    vector<int>arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    cout<<"Duplicate number is: "<<findDuplicate(arr)<<endl;//output duplicate number if arr is given as input arr=[1,3,4,2,2] and n is 5 => output is 2
    return 0;
}






// //method to find multiple duplicates using XOR
// // if more than one duplicate then we can use the same approach but we need to keep track of the count of each number and then XOR the numbers which have count more than 1.
#include<bits/stdc++.h>
using namespace std;
vector<int> findDuplicates(vector<int>& arr){
    int n=arr.size();
    vector<int>res;
    for(int i=0;i<n;i++){
        int idx=abs(arr[i])-1;
        if(arr[idx]<0){
            res.push_back(idx+1);
        }
        else{
            arr[idx]=-arr[idx];
        }
    }
    return res;
}
int main(){
    int n;
    cin>>n;
    vector<int>arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    vector<int>duplicates=findDuplicates(arr);
    cout<<"Duplicate numbers are: ";
    for(int x:duplicates){
        cout<<x<<" ";
    }
    cout<<endl;//output duplicate numbers if arr is given as input arr=[4,3,2,7,8,2,3,1] and n is 8 => output is 2 3
    return 0;
}



// // 🔹 BIT COUNTING & TRICKS
// // 5. Brian Kernighan’s Algorithm ⭐⭐⭐
// //application: Count set bits in a number
// // 💡 Idea
// // n & (n-1) removes last set bit
// // 📐 Complexity
// // O(number of set bits)
// draw run if n=10 (binary 1010):
// n=10 (1010) → n-1=9 (1001) → n & (n-1) = 8 (1000) → count=1
// n=8 (1000) → n-1=7 (0111) → n & (n-1) = 0 (0000) → count=2
// Total count = 2 (number of set bits in 10 is 2)





#include<bits/stdc++.h>
using namespace std;
// Count set bits using Brian Kernighan’s Algorithm
int countSetBits(int n){
    int cnt=0;
    while(n){
        n=n&(n-1);//remove last set bit
        cnt++;
    }
    return cnt;
}
int main(){
    int n;
    cin>>n;
    cout<<"Number of set bits in "<<n<<" is: "<<countSetBits(n)<<endl;//output number of set bits in n if n is given as input n=13 => output is 3 (binary representation of 13 is 1101 which has 3 set bits)
    return 0;
}



// // 6. Count Bits Efficiently (DP)
// // 💡 Idea
// // dp[i] = dp[i >> 1] + (i & 1)
// // 📐 Complexity
// // O(n)




#include<bits/stdc++.h>
using namespace std;
// Count bits from 1 to N using DP
vector<int>countBits(int n){
    vector<int>dp(n+1);
    for(int i=1;i<=n;i++){
        dp[i]=dp[i>>1]+(i&1);
    }
    return dp;
}
int main(){
    int n;
    cin>>n;
    vector<int>res=countBits(n);
    cout<<"Number of set bits from 1 to "<<n<<" are: ";
    for(int i=1;i<=n;i++){
        cout<<res[i]<<" ";
    }
    cout<<endl;//output number of set bits from 1 to n if n is given as input n=5 => output is 0 1 1 2 1 (number of set bits in 1 is 0, in 2 is 1, in 3 is 1, in 4 is 2, in 5 is 1)
    return 0;
}




// // 7. Count Bits from 1 to N
// // 💡 Idea
// // Use the pattern of bits in numbers
// // Count bits in groups of powers of 2
// // For each group of size 2^k, there are k * 2^(k-1) set bits
// // Count bits in the last incomplete group
// // 📐 Complexity
// // O(log n)
// // Pattern based counting
// // cycle = 1 << (i + 1)

// // full_cycles = n / cycle
// // count += full_cycles * (cycle / 2)

// // remainder = n % cycle
// // count += max(0, remainder - (cycle/2) + 1)





#include<bits/stdc++.h>
using namespace std;
// Check if i-th bit is set
bool isBitSet(int n,int i){
    return (n>>i)&1;
}
// Count set bits from 1 to n
int countSetBitsFrom1ToN(int n){
    int cnt=0;
    for(int i=0;i<32;i++){
        int group_size=1<<(i+1);
        int full_groups=(n+1)/group_size;
        cnt+=full_groups*(group_size/2);
        int remainder=(n+1)%group_size;
        cnt+=max(0,remainder-(group_size/2)+1);
    }
    return cnt;
}
int main(){
    int n;
    cin>>n;
    cout<<"Number of set bits from 1 to "<<n<<" is: "<<countSetBitsFrom1ToN(n)<<endl;//output number of set bits from 1 to n if n is given as input n=5 => output is 7 (binary representation of numbers from 1 to 5 are 1, 10, 11, 100, 101 which have total 7 set bits)
    return 0;
}



// //2ed method to count set bits from 1 to n using Brian Kernighan’s Algorithm
#include<bits/stdc++.h>
using namespace std;
long long countSetBitsFrom1ToN_2(int n){
    long long cnt = 0;
    for(int i=0;(1LL<<i)<=n;i++){
        long long cycle=1LL<<(i+1);
        long long full_cycles=(n+1)/cycle;
        cnt += full_cycles*(cycle/2);
        long long remainder = (n + 1) % cycle;
        cnt += max(0LL, remainder - (cycle / 2));
    }
    return cnt;
}

int main(){
    int n;
    cin >> n;
    cout << "Number of set bits from 1 to " << n 
         << " is: " << countSetBitsFrom1ToN_2(n) << endl;
    return 0;
}




// // 8. Generate All Subsets
// // 📐 Idea
// // Total subsets = 2^n
// // Each number from 0 to 2^n-1 represents a subset mask
// // For each bit in mask, check if it's set to include element
// // ⚙️ Approach
// // Loop from 0 to 2^n-1
// // For each mask, generate subset based on set bits in mask
// // Each number from 0 → 2^n-1 is a subset mask
// // For each bit in mask, check if it's set to include element in subset

// // Each number from 0 → 2^n-1 is a subset mask






#include<bits/stdc++.h>
using namespace std;
// Generate all subsets using bitmasking
void generateSubsets(vector<int>& arr){
    int n=arr.size();
    int total_subsets=1<<n; // 2^n subsets
    for(int mask=0;mask<total_subsets;mask++){
        vector<int>subset;
        for(int i=0;i<n;i++){
            if(mask & (1<<i)){ // if i-th bit is set in mask
                subset.push_back(arr[i]);
            }
        }
        // Print the subset
        cout<<"Subset: ";
        for(int x:subset){
            cout<<x<<" ";
    }
        cout<<endl;
    }
}
int main(){
    int n;
    cin>>n;
    vector<int>arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    generateSubsets(arr);//output all subsets of arr if arr is given as input arr=[1,2,3] and n is 3 => output is Subset:  (empty subset) Subset: 1 Subset: 2 Subset: 1 2 Subset: 3 Subset: 1 3 Subset: 2 3 Subset: 1 2 3
    return 0;
}




// // 9. Iterate Over Subsets
// // 💡 Advanced Trick
// // sub = (sub - 1) & mask
// // Iterate over all subsets of a given mask
// // Start with sub = mask
// // Loop until sub becomes 0
// // In each iteration, sub = (sub - 1) & mask gives the next subset





#include<bits/stdc++.h>
using namespace std;
// Iterate over all subsets of a given mask
void iterateSubsets(int mask){
    int sub=mask;
    while(sub){
        cout<<"Subset: "<<sub<<endl;
        sub=(sub-1)&mask; // get next subset
    }
}
int main(){
    int mask;
    cin>>mask;
    iterateSubsets(mask);//output all subsets of mask if mask is given as input mask=5 (binary 101) => output is Subset: 5 (binary 101) Subset: 4 (binary 100) Subset: 1 (binary 001)
    return 0;
}



// //10. Subset Sum using Bitmask
// // 💡 Idea
// // For each subset mask, calculate sum of included elements
// // Check if sum equals target
// // ⚙️ Approach
// // Loop from 0 to 2^n-1
// // For each mask, calculate subset sum based on set bits
// // Check if subset sum equals target



#include<bits/stdc++.h>
using namespace std;
// Check if subset with target sum exists using bitmasking
bool subsetSum(vector<int>&arr,int target){
    int n=arr.size();
    int total_subsets=1<<n; // 2^n subsets
    for(int mask=0;mask<total_subsets;mask++){
        int sum=0;
        for(int i=0;i<n;i++){
            if(mask & (1<<i)){ // if i-th bit is set in mask
                sum+=arr[i];
            }
            if(sum==target){
                return true;
            }
        }
    }
    return false;
}
int main(){
    int n,target;
    cin>>n>>target;
    vector<int>arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    cout<<"Is there a subset with target sum "<<target<<"? "<<(subsetSum(arr,target) ? "Yes" : "No")<<endl;//output if there is a subset with target sum if arr and target are given as input arr=[1,2,3] and target=5 => output is Yes (subset [2,3] has sum 5)
    return 0;
}




// // 🔹 RANGE & LOGIC PROBLEMS
// // 11. Bitwise AND of Range
// // 💡 Idea

// // Common prefix in binary representation of m and n
// // Shift m and n right until they are equal
// // Shift result left by number of shifts
// // ⚙️ Approach
// // Count number of shifts until m and n are equal
// // Shift m and n right in each iteration
// // When m and n become equal, that is the common prefix
// // Shift result left by number of shifts to get final answer
//draw run if m=5 (binary 101) and n=7 (binary 111):
// m=5 (101), n=7 (111) → m>>1=2 (10), n>>1=3 (11) → m>>1=1 (1), n>>1=1 (1) → m and n are equal (1)
// Number of shifts = 2





#include<bits/stdc++.h>
using namespace std;
// Bitwise AND of range [m, n]
int rangeBitwiseAnd(int m,int n){
    int shift=0;
    while(m!=n){
        m>>=1;
        n>>=1;
        shift++;
    }
    return m<<shift;
}
int main(){
    int m,n;
    cin>>m>>n;
    cout<<"Bitwise AND of range ["<<m<<", "<<n<<"] is: "<<rangeBitwiseAnd(m,n)<<endl;//output bitwise AND of range [m, n] if m and n are given as input m=5 and n=7 => output is 4 (binary representation of 5 is 101, 6 is 110, 7 is 111. Bitwise AND of 5, 6, and 7 is 100 which is 4 in decimal)
    return 0;
}




// // 12. Maximum XOR of Two Numbers ⭐⭐⭐
// // 💡 Idea

// // Use Trie (optimal) OR brutece (O(n^2))
// // For Trie, insert all numbers in binary form
// // For each number, find maximum XOR by traversing Trie
// // ⚙️ Approach
// // Build Trie of binary representations of numbers
// // For each number, traverse Trie to find maximum XOR
//draw run if arr=[3,10,5,25,2,8]:
// Insert 3 (binary 00011) into Trie
// Insert 10 (binary 01010) into Trie
// Insert 5 (binary 00101) into Trie
// Insert 25 (binary 11001) into Trie
// Insert 2 (binary 00010) into Trie
// Insert 8 (binary 01000) into Trie
// For 3, find max XOR in Trie → 3 ^ 25 = 28
// For 10, find max XOR in Trie → 10 ^ 5 = 15
// For 5, find max XOR in Trie → 5 ^ 25 = 28
// For 25, find max XOR in Trie → 25 ^ 5 = 28
// For 2, find max XOR in Trie → 2 ^ 25 = 27
// For 8, find max XOR in Trie → 8 ^ 25 = 17
// Maximum XOR is 28 (from pairs 5 and 25, or 3 and 25)
// Brute force approach: Check XOR of all pairs and keep track of maximum
// For each pair (i, j), calculate arr[i] ^ arr[j] and update maximum XOR if it's greater than current maximum
// Time complexity of brute force approach is O(n^2) and space complexity is O(1)
//total pairs = n*(n-1)/2, for each pair we calculate XOR and compare with maximum XOR found so far. This results in O(n^2) time complexity. Space complexity is O(1) as we are using only a constant amount of extra space to store the maximum XOR value.


#include<bits/stdc++.h>
using namespace std;
int maxXOR(vector<int>&arr){
    int max_xor=0;
    for(int i=0;i<arr.size();i++){
        for(int j=i+1;j<arr.size();j++){
            max_xor=max(max_xor,arr[i]^arr[j]);
        }
    }
    return max_xor;
}
int main(){
    int n;
    cin>>n;
    vector<int>arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    cout<<"Maximum XOR of two numbers in the array is: "<<maxXOR(arr)<<endl;//output maximum XOR of two numbers in arr if arr is given as input arr=[3,10,5,25,2,8] and n is 6 => output is 28 (maximum XOR is 5^25 = 28)
    return 0;
}






// // 13. Minimum XOR Pair
// // 💡 Idea
// // Sort the array
// // Sort → check adjacent pairs for minimum XOR
// // ⚙️ Approach
// // Sort the array
// // Loop through sorted array and calculate XOR of adjacent pairs
// // Keep track of minimum XOR




#include<bits/stdc++.h>
using namespace std;
// Find minimum XOR of any pair in the array
int minXORPair(vector<int>&arr){
    sort(arr.begin(),arr.end());
    int min_xor=INT_MAX;
    for(int i=1;i<arr.size();i++){
        min_xor=min(min_xor,arr[i]^arr[i-1]);
    }
    return min_xor;
}
int main(){
    int n;
    cin>>n;
    vector<int>arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    cout<<"Minimum XOR of any pair in the array is: "<<minXORPair(arr)<<endl;//output minimum XOR of any pair in arr if arr is given as input arr=[0,2,5,7] and n is 4 => output is 2 (minimum XOR is 5^7 = 2)
    return 0;
}



// // 14. Swap Two Numbers using XOR
// // 💡 Idea
// // a = a ^ b
// // b = a ^ b
// // a = a ^ b
// // ⚙️ Approach
// // Use XOR to swap values without temporary variable




#include<bits/stdc++.h>
using namespace std;
// Swap two numbers using XOR
void swap(int &a,int &b){
    a=a^b;
    b=a^b;
    a=a^b;
}
int main(){
    int a,b;
    cin>>a>>b;
    swap(a,b);
    cout<<"After swapping: a = "<<a<<", b = "<<b<<endl;//output swapped values of a and b if a and b are given as input a=5 and b=3 => output is After swapping: a = 3, b = 5
    return 0;
}




// // 15. Check if Differ by One Bit
// // 💡 Idea
// // x ^ y has only one set bit
// // Check if x ^ y is a power of 2
// // ⚙️ Approach
// // Calculate x ^ y
// // Check if result is a power of 2 (only one set bit)
// // Check if two numbers differ by exactly one bit
// // Calculate x ^ y
// // If x ^ y is a power of 2, then they differ by exactly one bit
// // A number is a power of 2 if it has exactly one set bit, which can be checked using the condition (n & (n - 1)) == 0 and n > 0
// // Check if x and y differ by exactly one bit
// // Calculate x ^ y
// // Check if x ^ y is a power of 2
// // A number n is a power of 2 if (n & (n - 1)) == 0 and n > 0
// // Therefore, to check if x and y differ by exactly one bit, we can calculate x ^ y and check if it is a power of 2 using the condition (x ^ y) & ((x ^ y) - 1) == 0 and (x ^ y) > 0
// // Check if two numbers differ by exactly one bit
// // Calculate x ^ y



#include<bits/stdc++.h>
using namespace std;
// Check if two numbers differ by exactly one bit
bool differByOneBit(int x,int y){
    int xor_val=x^y;
    return (xor_val & (xor_val-1))==0 && xor_val>0;
}
int main(){
    int x,y;
    cin>>x>>y;
    cout<<"Do "<<x<<" and "<<y<<" differ by exactly one bit? "<<(differByOneBit(x,y) ? "Yes" : "No")<<endl;//output if x and y differ by exactly one bit if x and y are given as input x=5 and y=7 => output is Yes (binary representation of 5 is 101 and 7 is 111, they differ by exactly one bit which is the second bit from the right)
    return 0;
}