Readme

3022.Minimize-OR-of-Remaining-Elements-Using-Operations

本题的时间复杂度要求o(n)，单纯用one pass很难求解。此时可以考虑到引入常数量，来适当松弛时间复杂度的要求。比如说，本题任何一个数字的二进制位不超过30，那么可以尝试类似o(30n)的解法。事实上，求解本题的突破口就在于逐位构造。

我们现在只考虑最高位，我们希望最终结果是0的话，那么意味着你需要将数组分割成若干个区间，每个区间内的AND结果都是0（这样，区间彼此之间的OR的结果才能是0）。这样的分割方法可能有很多种，但是我们并不需要关心具体的操作，只需要判定“能否实现”即可。这个可以用贪心法解决。从左往右依次处理，如果有非零元素，那么我们必然将其与右边的元素进行AND操作，重复进行直至变成0。此时所扫过的区间就是我们想要的一个最小区间。这是因为我们有贪心的思想：分割的每个区间越小，即总区间的数目越多，就意味着我们需要的AND操作最少。这是因为AND的总操作数本质就是n减去区间的数目。

我们如果用上述的方法，判定出“最高位不能够构造出0”，那么我们就直接将result的最高位放置1即可。在后续的分析中，我们都不需要考虑nums数组里任何元素的最高位。它们不会对我们后续的构造（即区间分割）带来负面的“牵制”（已经摆烂了），即任何区间分割的方法都不会使得result的最高位能变成0。

我们如果用上述的方法，判定出“最高位能够构造出0”，此时需要注意：符合条件的分割可能有很多种策略，但我们不关心具体的操作，因为最优的分割需要结合到次高位的制约。接下来我们就考察次高位，依然是尝试判断“能否在该位构造出0”。这时候我们要注意，因为贪心，我们必须仍然要保持最高位的结果是0，同时也希望次高位的结果也是0，所以本质就是判断“仅考虑最高的两个bit位的前提下，能否将数组风格成若干个区间，每个区间内的AND结果都是00”。如果结论是true，就意味着最终result的次高位也直接置0，否则最终result的次高位置1. 接下来，重复策略，如果刚才的结论是true，我们接下来会尝试能否在最高的三位构造出000；如果是false，那么之后的考察就要忽略掉所有元素的次高位（任何分割都不会是的result的次高位变成0）。

以此类推，通过查看数组能否被分割成若干个AND为0的区间（仅限前对应二进制的前缀），可以从高到低判定是否能在result里的每个bit上置零。如果不能，记得将nums里所有元素的该bit位直接划去。