Skip to content

3825. Longest Strictly Increasing Subsequence With Non-Zero Bitwise AND

SourceBiweekly Contest 175 Q3DifficultyMediumRating1845

Description

You are given an integer array nums.

Return the length of the longest strictly increasing subsequence in nums whose bitwise AND is non-zero. If no such subsequence exists, return 0.

 

Example 1:

Input: nums = [5,4,7]

Output: 2

Explanation:

One longest strictly increasing subsequence is [5, 7]. The bitwise AND is 5 AND 7 = 5, which is non-zero.

Example 2:

Input: nums = [2,3,6]

Output: 3

Explanation:

The longest strictly increasing subsequence is [2, 3, 6]. The bitwise AND is 2 AND 3 AND 6 = 2, which is non-zero.

Example 3:

Input: nums = [0,1]

Output: 1

Explanation:

One longest strictly increasing subsequence is [1]. The bitwise AND is 1, which is non-zero.

 

Constraints:

  • 1 <= nums.length <= 105
  • 0 <= nums[i] <= 109​​​​​​​

Solutions

Solution 1: Enumeration + Longest Increasing Subsequence

Thinking

We want the longest strictly increasing subsequence whose AND is nonzero. \(n \le 10^5\), and a plain LIS ignores the AND.

A nonzero AND means some bit is \(1\) in every chosen value.

Enumerate that bit, keep numbers with the bit set, and run LIS on the filtered sequence.

About \(30\) bits, each an \(O(n \log n)\) LIS, and we take the maximum.

A non-zero bitwise AND result means that all numbers in the subsequence have a \(1\) at a certain bit position. We can enumerate that bit position, then find the longest strictly increasing subsequence among all numbers that have a \(1\) at that bit position, and take the maximum value across all enumerations as the answer.

The time complexity is \(O(\log M \times n \times \log n)\), and the space complexity is \(O(n)\). Here, \(n\) and \(M\) are the length of the array and the maximum value in the array, respectively.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def longestSubsequence(self, nums: List[int]) -> int:
        def lis(arr: List[int]) -> int:
            g = []
            for x in arr:
                j = bisect_left(g, x)
                if j == len(g):
                    g.append(x)
                else:
                    g[j] = x
            return len(g)

        ans = 0
        m = max(nums).bit_length()
        for i in range(m):
            arr = [x for x in nums if x >> i & 1]
            ans = max(ans, lis(arr))
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
    public int longestSubsequence(int[] nums) {
        int ans = 0;
        int mx = 0;
        for (int x : nums) {
            mx = Math.max(mx, x);
        }
        int m = 32 - Integer.numberOfLeadingZeros(mx);
        for (int i = 0; i < m; i++) {
            List<Integer> arr = new ArrayList<>();
            for (int x : nums) {
                if (((x >> i) & 1) == 1) {
                    arr.add(x);
                }
            }
            ans = Math.max(ans, lis(arr));
        }
        return ans;
    }

    private int lis(List<Integer> arr) {
        List<Integer> g = new ArrayList<>();
        for (int x : arr) {
            int l = 0, r = g.size();
            while (l < r) {
                int mid = (l + r) >>> 1;
                if (g.get(mid) >= x) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }
            if (l == g.size()) {
                g.add(x);
            } else {
                g.set(l, x);
            }
        }
        return g.size();
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    int longestSubsequence(vector<int>& nums) {
        auto lis = [&](const vector<int>& arr) {
            vector<int> g;
            for (int x : arr) {
                auto it = lower_bound(g.begin(), g.end(), x);
                if (it == g.end()) {
                    g.push_back(x);
                } else {
                    *it = x;
                }
            }
            return (int) g.size();
        };

        int ans = 0;
        int mx = ranges::max(nums);
        int m = mx == 0 ? 0 : 32 - __builtin_clz(mx);

        for (int i = 0; i < m; ++i) {
            vector<int> arr;
            ranges::copy_if(nums, back_inserter(arr), [&](int x) {
                return (x >> i) & 1;
            });
            ans = max(ans, lis(arr));
        }

        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func longestSubsequence(nums []int) int {
    ans := 0
    m := bits.Len(uint(slices.Max(nums)))
    for i := 0; i < m; i++ {
        arr := make([]int, 0)
        for _, x := range nums {
            if (x>>i)&1 == 1 {
                arr = append(arr, x)
            }
        }
        ans = max(ans, lis(arr))
    }
    return ans
}

func lis(arr []int) int {
    g := make([]int, 0)
    for _, x := range arr {
        j := sort.SearchInts(g, x)
        if j == len(g) {
            g = append(g, x)
        } else {
            g[j] = x
        }
    }
    return len(g)
}

Comments