Horje
Find Minimum Bitwise XOR By Removing Atmost One Element

Given an array A[] of length N. Then your task is to output the minimum possible bitwise XOR that can be obtained by removing at most one element.

Examples:

Input: N = 4, A[] = {2, 4, 3, 6}
Output: 0
Explanation: If we element 3 is removed from A[], then up updated A[] will be: {2, 4, 6}. Then cumulative bitwise XOR = (2^4^6) = 0. Which is minimum possible.

Input: N = 2, A[] = {1, 1}
Output: 0
Explanation: No need to remove any element. Bitwise XOR is minimum already.

Approach: We can solve this problem using below idea:

First calculate the XOR of all elements in A[] in a variable let say X. Then iterate on A[] using loop and find the minimum possible value of (X^Ai) among all iterations.

Steps were taken to solve the problem:

  • Create a variable let say Min_XOR and Cum_XOR, initialize them as Integer.MIN_VALUE and 0 respectively.
  • Run a loop to iterate A[] and Initialize cumulative XOR.
  • Run a loop from i = 0 to i < N and follow below mentioned steps under the scope of loop:
    • Temp = Cum_XOR ^ A[i]
    • Min_XOR = min(Min_XOR, temp)
  • Return Min_XOR.

Below is the implementation of the above idea:

C++

#include <iostream>
#include <bits/stdc++.h>
 
using namespace std;
 
// Method to return min possible XOR
int MinXOR(int N, vector<int>& A)
{
    // Variable to store min XOR
    int Min_XOR = INT_MAX;
 
    // Variable to store Cumulative XOR of A[]
    int Cum_XOR = 0;
 
    // Loop to initialize cumulative XOR
    for (int element : A) {
        Cum_XOR ^= element;
    }
 
    // Iterating over A[] and checking
    // If we are removing A[i] from Cum_XOR
    // then XOR will be equal to temp
    for (int i = 0; i < N; i++) {
        int temp = Cum_XOR ^ A[i];
 
        // Updating Min_XOR
        Min_XOR = min(Min_XOR, temp);
    }
 
    Min_XOR = min(Min_XOR, Cum_XOR);
 
    // Returning Min possible XOR
    return Min_XOR;
}
 
// Driver Function
int main()
{
    // Input
    int N = 5;
    vector<int> A = {1, 3, 5, 17, 9};
 
    // Function call
    cout << MinXOR(N, A) << endl;
 
    return 0;
}
 
// This code is contributed by shivamgupta310570

Java

// Java code to implement the approach
 
import java.io.*;
import java.lang.*;
import java.util.*;
 
// Driver Class
class GFG {
 
    // Driver Function
    public static void main(String[] args)
        throws java.lang.Exception
    {
        // Input
        int N = 5;
        int[] A = { 1, 3, 5, 17, 9 };
 
        // Function call
        System.out.println(MinXOR(N, A));
    }
 
    // Method to return min possible XOR
    public static int MinXOR(int N, int[] A)
    {
        // variable to store min XOR
        int Min_XOR = Integer.MAX_VALUE;
 
        // Variable to store Cumulative XOR of A[]
        int Cum_XOR = 0;
 
        // Loop to initialize cumulative XOR
        for (int element : A) {
            Cum_XOR ^= element;
        }
 
        // Iterating over A[] and checking
        // If we are removing A[i] from Cum_XOR
        // then XOR will be equal to temp
        for (int i = 0; i < N; i++) {
            int temp = Cum_XOR ^ A[i];
 
            // Updating Min_XOR
            Min_XOR = Math.min(Min_XOR, temp);
        }
 
        Min_XOR = Math.min(Min_XOR, Cum_XOR);
 
        // Returning Min possible XOR
        return Min_XOR;
    }
}

Python3

# Python code for the above approach
 
# Method to return min possible XOR
def min_xor(n, arr):
    # Variable to store min XOR
    min_xor_value = float('inf')
 
    # Variable to store Cumulative XOR of arr
    cum_xor = 0
 
    # Loop to initialize cumulative XOR
    for element in arr:
        cum_xor ^= element
 
    # Iterating over arr and checking
    # If we are removing arr[i] from cum_xor
    # then XOR will be equal to temp
    for i in range(n):
        temp = cum_xor ^ arr[i]
 
        # Updating min_xor_value
        min_xor_value = min(min_xor_value, temp)
 
    min_xor_value = min(min_xor_value, cum_xor)
 
    # Returning Min possible XOR
    return min_xor_value
 
# Driver Code
if __name__ == "__main__":
    # Input
    N = 5
    A = [1, 3, 5, 17, 9]
 
    # Function call
    print(min_xor(N, A))

C#

using System;
 
using System.Collections.Generic;
 
class Program
 
{
 
    // Method to return min possible XOR
 
    static int MinXOR(int N, List<int> A)
 
    {
 
        // Variable to store min XOR
 
        int Min_XOR = int.MaxValue;
 
        // Variable to store Cumulative XOR of A[]
 
        int Cum_XOR = 0;
 
        // Loop to initialize cumulative XOR
 
        foreach (int element in A)
 
        {
 
            Cum_XOR ^= element;
 
        }
 
        // Iterating over A[] and checking
 
        // If we are removing A[i] from Cum_XOR
 
        // then XOR will be equal to temp
 
        for (int i = 0; i < N; i++)
 
        {
 
            int temp = Cum_XOR ^ A[i];
 
            // Updating Min_XOR
 
            Min_XOR = Math.Min(Min_XOR, temp);
 
        }
 
        Min_XOR = Math.Min(Min_XOR, Cum_XOR);
 
        // Returning Min possible XOR
 
        return Min_XOR;
 
    }
 
    // Driver Function
 
    static void Main(string[] args)
 
    {
 
        // Input
 
        int N = 5;
 
        List<int> A = new List<int> { 1, 3, 5, 17, 9 };
 
        // Function call
 
        Console.WriteLine(MinXOR(N, A));
 
    }
 
}

Javascript

// JavaScript Implementation
// Method to return min possible XOR
function minXOR(N, A) {
    // Variable to store min XOR
    let min_XOR = Number.MAX_SAFE_INTEGER;
 
    // Variable to store Cumulative XOR of A[]
    let cum_XOR = 0;
 
    // Loop to initialize cumulative XOR
    for (let element of A) {
        cum_XOR ^= element;
    }
 
    // Iterating over A[] and checking
    // If we are removing A[i] from Cum_XOR
    // then XOR will be equal to temp
    for (let i = 0; i < N; i++) {
        let temp = cum_XOR ^ A[i];
 
        // Updating min_XOR
        min_XOR = Math.min(min_XOR, temp);
    }
 
    min_XOR = Math.min(min_XOR, cum_XOR);
 
    // Returning min possible XOR
    return min_XOR;
}
 
// Driver Function
 
// Input
let N = 5;
let A = [1, 3, 5, 17, 9];
 
// Function call
console.log(minXOR(N, A));
 
// This code is contributed by Tapesh(tapeshdu420)

Output

14

Time Complexity: O(N)
Auxiliary Space: O(1)


 


Reffered: https://www.geeksforgeeks.org

Bit Magic

Related
Maximum Strings Concatenation Maximum Strings Concatenation
XOR Graph Minimum Spanning Tree XOR Graph Minimum Spanning Tree
Find the value of X and Y such that X Bitwise XOR Y equals to (X+Y)/2 Find the value of X and Y such that X Bitwise XOR Y equals to (X+Y)/2
XOR of Bitwise OR Pairs from Two Arrays XOR of Bitwise OR Pairs from Two Arrays
Find two numbers whose difference is given as Binary string Find two numbers whose difference is given as Binary string

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 13



 

Horje