334二进制尾零子数组问题

题目描述

要求在一个由正整数组成的数组中找到一个最短的连续子数组，使得该子数组中所有元素的乘积在二进制表示中至少有 k 个连续的 0，即乘积是 2^k 的倍数。如果不存在这样的子数组，则返回 -1。

解题思路

1. 因子 2 的计数：

   • 乘积为 2^k 的倍数，等价于乘积中包含至少 k 个因子 2。

2. 滑动窗口：

   • 使用双指针l和r来维护一个滑动窗口。l表示窗口的左端，r表示窗口的右端。
   • 遍历数组，逐步扩大右端r，将当前元素的因子 2 数量加到cnt2。
   • 当cnt2达到或超过k时，尝试缩小左端l，以找到最短满足条件的子数组长度。每次缩小时，减去左端元素的因子 2 数量，并移动左指针。

代码实现

def solution(n: int, k: int, a: list) -> int:
    def div(x):
        cnt2 = 0
        while x % 2 == 0:
            x //= 2
            cnt2 += 1
        return cnt2
    res = n + 1
    cnt2 = l = 0
    for r, x in enumerate(a):
        cnt2 += div(x)
        while cnt2 - div(a[l]) >= k and l < r:
            cnt2 -= div(a[l])
            l += 1
        if cnt2 >= k:
            res = min(res, r - l + 1)

    return res if res < n + 1 else -1


if __name__ == '__main__':
    print(solution(n = 6, k = 3, a = [1, 2, 3, 4, 5, 6]) == 3)
    print(solution(n = 5, k = 2, a = [10, 2, 8, 5, 4]) == 1)
    print(solution(n = 4, k = 4, a = [1, 3, 5, 7]) == -1)

复杂度分析

• 时间复杂度：O(n)，其中n是数组的长度。每个元素最多被遍历两次（一次作为右端，一次作为左端）。
• 空间复杂度：O(1)，只使用了常数级别的额外空间。