898. subarray bitwise OR operation

Preface

C++ It's a high-level programming language , from C Language expansion and upgrading , As early as 1979 By Benjani · Strauss LUP is AT&T Developed by Bell studio .
C++ Both can be carried out C Process programming of language , It can also be used for object-based programming characterized by abstract data types , It can also carry out object-oriented programming characterized by inheritance and polymorphism .C++ Good at object-oriented programming at the same time , You can also do process based programming .
C++ Have the practical characteristics of computer operation , At the same time, it is also committed to improving the programming quality of large-scale programs and the problem description ability of programming languages .

Java Is an object-oriented programming language , Not only absorbed C++ The advantages of language , It's abandoned C++ The incomprehensible inheritance in 、 Concepts such as pointer , therefore Java Language has two characteristics: powerful and easy to use .Java As the representative of static object-oriented programming language , Excellent implementation of object-oriented theory , Allow programmers to do complex programming in an elegant way of thinking .
Java It's simple 、 object-oriented 、 Distributed 、 Robustness, 、 Security 、 Platform independence and portability 、 Multithreading 、 Dynamic and so on .Java Can write desktop applications 、Web Applications 、 Distributed system and embedded system applications, etc .

Python By Guido of the Dutch Society for mathematical and computer science research · Van rosum On 1990 It was designed in the early 's , As a course called ABC A substitute for language .Python Provides efficient advanced data structure , It's also a simple and effective way of object-oriented programming .Python Syntax and dynamic types , And the nature of interpretative language , Make it a programming language for scripting and rapid application development on most platforms , With the continuous update of the version and the addition of new language features , Gradually used for independent 、 Development of large projects .
Python The interpreter is easy to extend , have access to C Language or C++（ Or something else can be done through C Calling language ） Expand new functions and data types .Python It can also be used as an extensible programming language in customizable software .Python Rich library of standards , Provides source code or machine code for each major system platform .
2021 year 10 month , Compiler for language popularity index Tiobe take Python Crowned the most popular programming language ,20 Put it in... For the first time in years Java、C and JavaScript above .

describe

We have an array of nonnegative integers arr .

For each （ Successive ） Subarray sub = [arr[i], arr[i + 1], ..., arr[j]] （ i <= j）, We are right. sub Each element in is bitwise or manipulated , Get the results arr[i] | arr[i + 1] | ... | arr[j] .

Returns the number of possible results . Multiple results are calculated only once in the final answer .

Example 1：

Input ：arr = [0]
Output ：1
explain ：
There is only one possible result 0 .

Example 2：

Input ：arr = [1,1,2]
Output ：3
explain ：
The possible subarray is [1],[1],[2],[1, 1],[1, 2],[1, 1, 2].
The result is 1,1,2,1,3,3 .
There are three unique values , So the answer is 3 .

Example 3：

Input ：arr = [1,2,4]
Output ：6
explain ：
The possible result is 1,2,3,4,6, as well as 7 .

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/bitwise-ors-of-subarrays
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Method 1 ： aggregate

analysis

obviously , The easiest way to do this is to enumerate all that satisfy i <= j Of (i, j), And calculate the different result(i, j) = A[i] | A[i + 1] | ... | A[j] The number of . because result(i, j + 1) = result(i, j) | A[j + 1], So we can O(N2)O(N^2)O(N2) The time complexity of all result(i, j), among NNN It's an array A The length of .

Let's try to optimize the simplest enumeration method . You can find , For fixed j,result(j, j), result(j - 1, j), result(j - 2), j, ..., result(1, j) The value of is monotonic , Because the result(k, j) Yes A[k - 1] To do a bit or operation , The result result(k - 1, j) It will not get smaller . also , According to the nature of bitwise or operational , If you put result(k, j) and result(k - 1, j) Are expressed in binary , Then the latter will represent several of the binary representations of the former 0 Turned into 1.

Because of arrays A Are less than 10^9 The positive integer , Their binary representation is at most 32 position . So from result(j, j) Start to result(1, j) end , At most, there will only be 32 individual 0 Turned into 1, in other words ,result(j, j), result(j - 1, j), result(j - 2), j, ..., result(1, j) At most 32 A different number . So we can maintain a collection , Store all to j For the end of result value . When ending from j Enumerate to j + 1 when , We will set each pair of numbers in the set A[j + 1] To do a bit or operation , Get new result The value will not exceed 32 individual .

Algorithm

We use a set cur Store in j For the end of result value , That is to say, all are satisfied i <= j Of A[i] | ... | A[j] Value . The size of the collection will not exceed 32.

author ：LeetCode
link ：https://leetcode.cn/problems/bitwise-ors-of-subarrays/solution/zi-shu-zu-an-wei-huo-cao-zuo-by-leetcode/
source ： Power button （LeetCode）
The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .

class Solution {
    public int subarrayBitwiseORs(int[] A) {
        Set<Integer> ans = new HashSet();
        Set<Integer> cur = new HashSet();
        cur.add(0);
        for (int x: A) {
            Set<Integer> cur2 = new HashSet();
            for (int y: cur)
                cur2.add(x | y);
            cur2.add(x);
            cur = cur2;
            ans.addAll(cur);
        }

        return ans.size();
    }
}


 author ：LeetCode
 link ：https://leetcode.cn/problems/bitwise-ors-of-subarrays/solution/zi-shu-zu-an-wei-huo-cao-zuo-by-leetcode/
 source ： Power button （LeetCode）
 The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .