题目描述
小欧拿到了一个数组,她准备选择一个连续子数组,满足该连续子数组的所有元素乘积的2
进制末尾至少有k
个0
。小红想知道,这个连续子数组的最短长度是多少?
输入描述
第一行输入两个正整数n
和k
。第二行输入n
个正整数ai
。
输出描述
一个整数,代表连续子数组的最短长度。如果不存在这样的子数组,输出-1。
示例一
输入
6 3
1 2 3 4 5 6
输出
3
说明
取[2,3,4]
即可,2*3*4=24
,其二进制为11000
。
示例二
输入
6 4
2 2 2 1 4 8
输出
2
示例三
输入
5 1
1 1 1 1 1
输出
-1
解题思路
2进制末尾的0代表什么
实际上,如果一个数的二进制末尾存在k
个0
,说明这个数是2
的k
次方即2^k
的倍数。
比如数字24
,其二进制为11000
,末尾存在3
个0
,说明24
是2^3 = 8
的倍数。
故题目可以简化为,找到最短的连续子数组,这个子数组的乘积是2
的k
次方即2^k
的倍数。
子数组乘积与2的k次方的关系
由于对连续子数组的操作是相乘,只有包含质因数2
的元素,才会对整个子数组的相乘结果造成影响。因此我们可以对数组中的每一个元素进行质因数分解,只考虑每个元素的质因数中2
的个数,得到相应的数组nums_contain_2
。
以原数组 nums = [1, 2, 3, 4, 5, 6]
为例,我们可以得到每个元素的质因数中2
的个数的数组nums_contain_2 = [0, 1, 0, 2, 0, 1]
。
故问题可以进一步简化为,找到nums_contain_2
的最短的连续子数组,该数组的和至少为k
。这就是一个非常典型的滑动窗口问题了。
代码
# 题目:【不定滑窗】OPPO2023秋招提前批-小欧的区间取数
# 作者:闭着眼睛学数理化
# 算法:不定滑窗
# 答疑微信:od1336
from math import inf
# 计算数字num包含多少个质因数2的函数
def get_num_contain_2(num):
# 初始化个数为2
ans = 0
# 如果num可以整除2,持续循环
# 整除2,同时ans递增1
while(num % 2 == 0):
num //= 2
ans += 1
return ans
n, k = map(int, input().split())
nums = list(map(int, input().split()))
# 获得nums数组中每一个元素,包含质因数2的个数
nums_contain_2 = [get_num_contain_2(num) for num in nums]
# 初始化答案、滑窗中质因数2的个数、左指针
ans = inf
windows_contain_2 = 0
left = 0
for right, num in enumerate(nums_contain_2):
# A1
windows_contain_2 += num
# A2
if windows_contain_2 >= k:
while windows_contain_2 >= k:
windows_contain_2 -= nums_contain_2[left]
left += 1
# A3
ans = min(ans, right-left+2)
print(ans if ans != inf else -1)
---END---