Skip to content

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

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

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