CODEWITHSUNDEEP
arraysbitwise-operatorssubsequencebitwise-or
Pranay Nagpure
Pranay Nagpure

Reputation: 11

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

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)?

Upvotes: 0

Views: 950

Answers (3)

Lalit Dhakad
Lalit Dhakad

Reputation: 1

The logic is simple. Add all newly computed bitwise or operation results into the set and use it for next element:

    int findSmallestMissingNumber(vector<int>& arr) {
            unordered_set<int> reachable;
            reachable.insert(0);
        
            for (int num : arr) {
                unordered_set<int> newCurrent = {num}; 
                for (int val : reachable) {
                    newCurrent.insert(val | num); 
                }
                reachable.insert(newCurrent.begin(), newCurrent.end()); 
            }
        
            int smallestMissing = 0;
            while (reachable.count(smallestMissing)) {
                ++smallestMissing;
            }
            
            return smallestMissing;
        }

Upvotes: 0

Ajay Singh
Ajay Singh

Reputation: 171

Since the OR function requires set bits or powers of 2, the first power of 2 which is not in the array should be the answer? For example if we have [1, 2, 4] then 1, 2, ..., 7 are all possible although 8 is not hence that is the answer.

Upvotes: 0

Anbu Anbu
Anbu Anbu

Reputation: 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)

Upvotes: 0

Related Questions