Given an array arr[] containing N positive integers, the task is to add an integer such that the bitwise Xor of the new array becomes K.
Examples:
Input: arr[] = {1, 4, 5, 6}, K = 4
Output: 2
Explanation: Bit-wise XOR of the array is 6.
And bit-wise XOR of 6 and 2 is 4.Input: arr[] = {2, 7, 9, 1}, K = 5
Output: 8
Approach: The solution to the problem is based on the following idea of bitwise Xor:
If for two numbers X and Y, the bitwise Xor of X and Y is Z then the bitwise Xor of X and Z is Y.
Follow the steps to solve the problem:
- Let the bitwise XOR of the array elements be X.
- Say the required value to be added is Y such that X Xor Y = K.
- From the above observation, it is clear that the value to be added (Y) is the same as X Xor K.
Below is the implementation of the above approach:
C++
// C++ code to implement the above approach#include <bits/stdc++.h>using namespace std;// Function to find the required valueint find_K(int K, vector<int>& arr){ int XOR = 0; // Find XOR of all the array elements for (int i = 0; i < arr.size(); i++) XOR ^= arr[i]; // K = XOR^N, where N is size of array return XOR ^ K;}// Drivers codeint main(){ int K = 4; vector<int> arr = { 1, 4, 5, 6 }; // Function call cout << find_K(K, arr); return 0;} |
Java
// Java code to implement the above approachimport java.io.*;class GFG { // Function to find the required value public static int find_K(int K, int arr[]) { int XOR = 0; // Find XOR of all the array elements for (int i = 0; i < arr.length; i++) XOR ^= arr[i]; // K = XOR^N, where N is size of array return XOR ^ K; } // Driver Code public static void main(String[] args) { int K = 4; int arr[] = { 1, 4, 5, 6 }; // Function call System.out.print(find_K(K, arr)); }}// This code is contributed by Rohit Pradhan |
Python3
# Python code to implement the above approach# Function to find the required valuedef find_K(K, arr): XOR = 0 # Find XOR of all the array elements for i in range(len(arr)): XOR ^= arr[i] # K = XOR^N, where N is size of array return XOR ^ K# Drivers codeK = 4arr = [ 1, 4, 5, 6 ]# Function callprint(find_K(K, arr))# This code is contributed by shinjanpatra |
C#
// C# code to implement the above approachusing System;class GFG{ // Function to find the required value static int find_K(int K, int[] arr) { int XOR = 0; // Find XOR of all the array elements for (int i = 0; i < arr.Length; i++) XOR ^= arr[i]; // K = XOR^N, where N is size of array return XOR ^ K; } // Driver Code public static int Main() { int K = 4; int[] arr = new int[] { 1, 4, 5, 6 }; // Function call Console.Write(find_K(K, arr)); return 0; }}// This code is contributed by Taranpreet |
Javascript
<script> // JavaScript code to implement the above approach // Function to find the required value const find_K = (K, arr) => { let XOR = 0; // Find XOR of all the array elements for (let i = 0; i < arr.length; i++) XOR = (XOR ^ arr[i]); // K = XOR^N, where N is size of array return (XOR ^ K); } // Drivers code let K = 4; let arr = [1, 4, 5, 6]; // Function call document.write(find_K(K, arr));// This code is contributed by rakeshsahni</script> |
Output
2
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
