find smallest whole number missing form bitwise OR of all the subsequence of given array?

Question

as the question suggests we need to find OR of all the subsequence of given array

`arr = { 1,3,4,0} `
bitwise OR of all subsequence
`[0] =>  0
[4]  => 4
[4, 0] => 4
[3]  => 3
[3, 0] => 3
[3, 4] => 7
[3, 4, 0] => 7
[1] => 1
[1, 0] => 1
[1, 4] => 5
[1, 4, 0] => 5
[1, 3] => 3
[1, 3, 0] => 3
[1, 3, 4] => 7
[1, 3, 4, 0] => 7`

so bitwise OR of all the subsequence is 
`{0,1,3,4,5,7}`
exclude repeated, **smallest missing whole** no is 2


now `1<= array.length <= 10^5 and 0<= arr[i] <= 10^5`

how do you solve this with an optimized approach, not exponential complexity (without generating all the subsequnce)?

Answer 1

The logic is simple.

• step-1. Find All possible subSequences and calculate a bitwise on each subSequence we found and then store values in list(bitwRes).
• step-2. Sort the list(bitwRes).
• step-3. take the first value+1 from List(bitwRes) and check whether available or not in the list(bitwRes) if there increment by 1. -step-3 executes until we didn't find the value smallest missing whole number.

`

    public int findSmalestWholeNumber(List<Integer> list){

      List<Integer> bitwRes = new ArrayList<Integer>();     
      subSeq(0, list, new ArrayList<Integer>(), bitwRes);
      Collections.sort(bitwRes);
            
      int j = bitwRes.get(0);
      for(int i=1; i<bitwRes.size(); i++)
      {
        if(bitwRes.contains(j++))
            continue;
        else {
            return --j;     
            break;
        }               
    }
    return 0;
    }

    public static void subSeq(int i, List<Integer> list, List<Integer> ds, List<Integer> bitwRes){

      if(i>=list.size())
      {
        // Doing-Biwise OR operations 
         int add = 0;
         for(int j: ds) {
            add |= j;
        }
        bitwRes.add(add);
        return;
       }
    
       ds.add(list.get(i));
       subSeq(i+1, list, ds, bitwRes);
       ds.remove(list.get(i));
       subSeq(i+1, list, ds, bitwRes);
      }
    }

' #Java #StriverYoutube(Learned bit about Recursions by using your videosThanks)