Given two integers A and B, the task is to find the minimum possible size of the array whose MEX of the array is A and Bitwise XOR of all array elements is B.
Examples:
Input: A = 1, B = 1
Output: 3
Explanation: The array which can satisfy the given condition is {0, 3, 2} which is of minimum possible size i.e, 3.Input: A = 1, B = 999
Output: 2
Approach: The given problem can be solved by the following observations:
- As the MEX of the array should be A as all the elements over the range [0, A – 1] must be included.
- In order to make the XOR of all array elements as B, a few integers must be added to the array which can be classified into 3 cases. Suppose variable currXOR stores the value of XOR over the range [0, A – 1] which can be calculated using the approach discussed in this article.
- Case 1 where currXor = B. In this case, no integers are required to be added.
- Case 2 where currXor^B = A. In this case, since A cannot be added to the array, 2 integers must be added such that their XOR is A.
- In all the other cases, 1 integer must be added in order to make the XOR of the given array as B.
Therefore, the above problem can be solved by finding the XOR of all numbers from 0 to A-1 and checking for the above-mentioned cases.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the minimum size// of array with given MEX and XORint minimumSizeArr(int A, int B){ int currXor = 0; // Find the XOR of values from // 0 to A-1 int reminder = (A - 1) % 4; // If A is a multiple of 4 if (reminder == 0) currXor = A - 1; // If A % 4 gives remainder 1 else if (reminder == 1) currXor = 1; // If A % 4 gives remainder 2 else if (reminder == 2) currXor = A; // Initializing array size by A int minSize = A; // If XOR of all values of array // is equal to B if (currXor == B) return minSize; // If the required integer to be // added is equal to A else if (currXor ^ B == A) return minSize + 2; // Else any integer can be added else return minSize + 1;}// Driver Codeint main(){ int A = 1; int B = 999; cout << minimumSizeArr(A, B); return 0;} |
Java
// Java program for the above approachpublic class GFG { // Function to find the minimum size // of array with given MEX and XOR static int minimumSizeArr(int A, int B) { int currXor = 0; // Find the XOR of values from // 0 to A-1 int reminder = (A - 1) % 4; // If A is a multiple of 4 if (reminder == 0) currXor = A - 1; // If A % 4 gives remainder 1 else if (reminder == 1) currXor = 1; // If A % 4 gives remainder 2 else if (reminder == 2) currXor = A; // Initializing array size by A int minSize = A; // If XOR of all values of array // is equal to B if (currXor == B) return minSize; // If the required integer to be // added is equal to A else if ((currXor ^ B) == A) return minSize + 2; // Else any integer can be added else return minSize + 1; } // Driver Code public static void main (String[] args) { int A = 1; int B = 999; System.out.println(minimumSizeArr(A, B)); }}// This code is contributed by AnkThon |
Python3
# python program for the above approach# Function to find the minimum size# of array with given MEX and XORdef minimumSizeArr(A, B): currXor = 0 # Find the XOR of values from # 0 to A-1 reminder = (A - 1) % 4 # If A is a multiple of 4 if (reminder == 0): currXor = A - 1 # If A % 4 gives remainder 1 elif (reminder == 1): currXor = 1 # If A % 4 gives remainder 2 elif (reminder == 2): currXor = A # Initializing array size by A minSize = A # If XOR of all values of array # is equal to B if (currXor == B): return minSize # If the required integer to be # added is equal to A elif (currXor ^ B == A): return minSize + 2 # Else any integer can be added else: return minSize + 1# Driver Codeif __name__ == "__main__": A = 1 B = 999 print(minimumSizeArr(A, B))# This code is contributed by rakeshsahni |
C#
// C# program for the above approachusing System;public class GFG { // Function to find the minimum size // of array with given MEX and XOR static int minimumSizeArr(int A, int B) { int currXor = 0; // Find the XOR of values from // 0 to A-1 int reminder = (A - 1) % 4; // If A is a multiple of 4 if (reminder == 0) currXor = A - 1; // If A % 4 gives remainder 1 else if (reminder == 1) currXor = 1; // If A % 4 gives remainder 2 else if (reminder == 2) currXor = A; // Initializing array size by A int minSize = A; // If XOR of all values of array // is equal to B if (currXor == B) return minSize; // If the required integer to be // added is equal to A else if ((currXor ^ B) == A) return minSize + 2; // Else any integer can be added else return minSize + 1; } // Driver Code public static void Main () { int A = 1; int B = 999; Console.WriteLine(minimumSizeArr(A, B)); }}// This code is contributed by ihritik |
Javascript
<script>// Javascript program for the above approach// Function to find the minimum size// of array with given MEX and XORfunction minimumSizeArr(A, B){ let currXor = 0; // Find the XOR of values from // 0 to A-1 let reminder = (A - 1) % 4; // If A is a multiple of 4 if (reminder == 0) currXor = A - 1; // If A % 4 gives remainder 1 else if (reminder == 1) currXor = 1; // If A % 4 gives remainder 2 else if (reminder == 2) currXor = A; // Initializing array size by A let minSize = A; // If XOR of all values of array // is equal to B if (currXor == B) return minSize; // If the required integer to be // added is equal to A else if (currXor ^ (B == A)) return minSize + 2; // Else any integer can be added else return minSize + 1;}// Driver Codelet A = 1;let B = 999;document.write(minimumSizeArr(A, B));// This code is contributed by saurabh_jaiswal.</script> |
Output:
2
Time Complexity: O(1)
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!
