Minimum value that can’t be formed using OR of elements of the Array
Given an array of positive integers arr[]. The task is to Find the minimum positive value which cannot be formed using OR operator on any subset of the array.
Examples:
Input: arr[] = {2, 3}
Output: 1
Explanation: Since 1 is missing from array and we cannot make it using OR for any other subset of this array, so it is the minimum positive value.Input: arr[] = {1, 2, 4}
Output: 8
Explanation: 1, 2 and 4 are already there in the array. Other numbers which can be formed are 3(1|2), 5(1|4), 6(2|4), 7(1|2|4) where “|” represents OR. So in this case 8 is the minimum positive number which cannot be formed using the given array.
Naive Approach: The brute force approach of this problem is to generate all subsets of the array and store OR of every element in that subset. Find the minimum positive value which is not thereafter calculating the OR operator for all elements in each subset.
Time Complexity: O(2n) where n is the size of the array.
Auxiliary Space: O(n)
Observations:
- Case 1: If 1 is missing then it is the minimum possible number. As OR of any numbers greater than 1 cannot make 1. As or of 2 numbers is always greater or equal to that number.
- Case 2: Similarly by above logic if 1 is there and 2 is not there then 2 is the smallest number present.
Now after these two cases, we have a common pattern:
- Using 1 and 2 we can generate every number till 3. As {1|2 = 3} and 1 and 2 are already there.
- Using 1, 2 and 4 we can generate every number till 7. As { 1|2 = 3, 1|4 = 5, 2|4 = 6, 1|2|4 = 7} and 1, 2, 4 are already there.
- Using 1, 2, 4……..2k we can generate every number till 2k+1 – 1.
Efficient approach: To solve the problem follow the below idea:
The efficient approach to solve this problem is to find the smallest positive number 2k which is not present in the array. This is due to the fact that by using the numbers till a certain 2k, we can generate all numbers till the next 2k number using OR operators. In simpler words, if we have all the numbers till 2k then we can generate every number till 2k+1 -1. And hence due to this logic, we can only check of power of 2 which is missing, and ignore other elements.
Below are the steps for the above approach:
- Sort the array.
- Initialize a variable say, res = 1, to store the lowest possible value that cannot be formed by taking the OR of any subset of the array.
- Run a loop till 0 to n-1, check if (res == arr[i]), and update res = res*2, to find the next lowest number that is the power of 2 that is not present in the array.
- Return res.
Below is the code for the above approach:
C++
// C++ code for above approach #include <bits/stdc++.h> using namespace std; // Function to find the minimum positive // value which cannot be formed using OR // operator on any subset of the array. int min_or( int arr[], int n) { // Sorting the array sort(arr, arr + n); // Variable to store minimum // positive value int res = 1; for ( int i = 0; i < n; i++) { // Finding the lowest power of 2 // which is not present in the array if (res == arr[i]) res *= 2; } // Returning the lowest power of 2 // which is not present return res; } // Driver code int main() { int arr[] = { 1, 2 }; int n = ( sizeof (arr) / sizeof ( int )); // Function Call cout << min_or(arr, n); return 0; } |
Java
// Java code for above approach import java.util.Arrays; public class GFG { // Function to find the minimum positive // value which cannot be formed using OR // operator on any subset of the array. public static int min_or( int arr[], int n) { // Sorting the array Arrays.sort(arr); // Variable to store minimum positive value int res = 1 ; for ( int i = 0 ; i < n; i++) { // Finding the lowest power of 2 // which is not present in the array if (res == arr[i]) res *= 2 ; } // Returning the lowest power of 2 // which is not present return res; } // Driver code public static void main(String[] args) { int arr[] = { 1 , 2 }; int n = arr.length; // Function Call System.out.println(min_or(arr, n)); } } |
Python3
# Python code for above approach # Function to find the minimum positive # value which cannot be formed using OR # operator on any subset of the array. def min_or(arr, n): # Sorting the array arr.sort() # Variable to store minimum # positive value res = 1 for i in range (n): # Finding the lowest power of 2 # which is not present in the array if res = = arr[i]: res * = 2 # Returning the lowest power of 2 # which is not present return res # Driver code if __name__ = = '__main__' : arr = [ 1 , 2 ] n = len (arr) # Function Call print (min_or(arr, n)) |
Javascript
// Javascript code for above approach // Function to find the minimum positive // value which cannot be formed using OR // operator on any subset of the array. function min_or(arr, n) { // Sorting the array arr.sort((a, b) => a - b); // Variable to store minimum positive value let res = 1; for (let i = 0; i < n; i++) { // Finding the lowest power of 2 which is not present in the array if (res === arr[i]) { res *= 2; } } // Returning the lowest power of 2 which is not present return res; } // Driver code const arr = [1, 2]; const n = arr.length; // Function call console.log(min_or(arr, n)); |
C#
// C# code for above approach using System; using System.Linq; public class GFG { // Function to find the minimum positive // value which cannot be formed using OR // operator on any subset of the array. public static int MinOR( int [] arr, int n) { // Sorting the array Array.Sort(arr); // Variable to store minimum positive value int res = 1; for ( int i = 0; i < n; i++) { // Finding the lowest power of 2 which is not // present in the array if (res == arr[i]) res *= 2; } // Returning the lowest power of 2 which is not // present return res; } public static void Main() { int [] arr = { 1, 2 }; int n = arr.Length; // Function Call Console.WriteLine(MinOR(arr, n)); } } |
4
Time Complexity: O(n*log(n)) where n is the size of the array.
Auxiliary Space: O(1)