Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

2044. Count the number of subsets by bit or that can get the maximum value

Statistics by bit or can get the maximum number of subsets, medium

I. Title Description:

What is the relationship between the input array and the return value? The examples are a little bit confusing

Then go back and look at the first sentence of the original question. What was it about

I wonder if XDM has this feeling!!

Ii. Analysis of Ideas:

1. What ideas does this question examine? What’s your thinking?

So let’s take a closer look, what exactly does this problem need us to do? Let’s break it down step by step:

  • They’re going to give us an array, and we need to find subarrays of that array, non-empty subarrays
  • Computes the bitvalue or result of each subarray element and finds the largest subarray of the result data

And you can see, in doing this problem, we really want to make sure that we have this inclusion relationship, we want the innermost subarray of the largest bits or results

We can deduce this using the example in the question: take nums = [3,2,1,5]

In the figure above, we can convert the subarray of the array to the way of processing the bits. The length of the array is 4, we use 4 bits to represent the number. The corresponding position of the bit is 1, indicating that the corresponding position of the NUMS array is selected

If the corresponding position of the bit is 0, the corresponding position of the NUMS array is not selected

At this time, I can take the position of bit 1 in the subarray corresponding to the number in the array as a set, a total of 2 n power -1 sets, each set to calculate the result of bitwise or, and finally screen out the number of subarrays of bitwise or the largest value

2. Try coding

Based on the above logic and analysis, we can translate it into the following code

The encoding is as follows:

func countMaxOrSubsets(nums []int) int {
    maxOr := 0
    or := 0
    res := 0
    for i := 1; i< 1 << len(nums); i++ {
         or = 0
         for j,num := range nums {
            if (i >> j) & 1= =1 {
                 or = or | num
             } 
         }
         if or > maxOr {
             maxOr = or
             res = 1
         }else if or == maxOr {
            res++
         }else{}}return res

}
Copy the code
  • MaxOr is the maximum value recorded, and when this value is refreshed, the result set is updated to 1
  • Or represents the bitbit or result of the current collection
  • Res indicates the number of sets by bit or maximum
  • The first for loop in the code represents the number of polling sets
  • The second for loop, which polls the elements in the NUMS array, finds the elements in the set with bit 1, and evaluates the result by bit or

Iv. Summary:

In this case, the time complexity is relatively high, because each time we need to iterate over the length of the number group, the time complexity is:


O ( 2 n ∗ n ) O(2^n*n)

The space complexity is the length of the array O(n)

Count the number of subsets by bit or the maximum that can be obtained

Today is here, learning, if there is a deviation, please correct

Welcome to like, follow and favorites

Friends, your support and encouragement, I insist on sharing, improve the quality of the power

All right, that’s it for this time

Technology is open, our mentality, should be more open. Embrace change, live in the sun, and strive to move forward.

I am Nezha, welcome to like, see you next time ~