困难
给你一个长度为 n 的整数数组 nums 和一个整数 k。
令 x1, x2, ..., xn-k+1 按从左到右的顺序,依次表示 nums 中每个长度为 k 的 子数组 的 按位与 结果。
如果对于每个 1 <= i <= n - k + 1,都有 (y & xi) != 0,则称正整数 y 是 有效的。
返回所有 有效 整数 y 中 置位 数量的 最小值。如果不存在有效的整数,返回 -1。
置位 是指一个数的二进制表示中值为 1 的位。
子数组 是数组中连续的 非空 元素序列。
示例 1:
输入: nums = [6,7,3], k = 2
输出: 1
解释:
- 长度为
k = 2的两个子数组为[6, 7]和[7, 3]。 - 它们的按位与结果为
x1 = 6 & 7 = 6和x2 = 7 & 3 = 3。 y = 2是有效的,因为2 & 6 = 2且2 & 3 = 2,均不为零。y = 2有 1 个置位("010"),因此答案为 1。
示例 2:
输入: nums = [3,5,12], k = 1
输出: 2
解释:
- 由于
k = 1,每个子数组只有一个元素,因此x1 = 3,x2 = 5,x3 = 12。 y = 9是有效的,因为9 & 3 = 1,9 & 5 = 1,且9 & 12 = 8,均不为零。y = 9有 2 个置位("1001"),因此答案为 2。
示例 3:
输入: nums = [2,1], k = 2
输出: -1
解释:
- 长度为
k = 2的唯一子数组为[2, 1],其按位与结果为x1 = 2 & 1 = 0。 - 由于
x1 = 0,不存在有效的y。因此,答案为 -1。
提示:
1 <= n == nums.length <= 1051 <= k <= n0 <= nums[i] <= 105