Try to see the difference between two consecutive elements in the sequence below: 1, 2, 4, 8 ... 2^0, 2^1, 2^2, 2^3 ...
We are required to find the number of windows which could be increasing given the condition below:
- If you multiply the first element by 2^0, the second element by 2^1, ..., and the (k+1)-st element by 2k, then this subarray is sorted in a strictly increasing order.
Multiplying the first element by 2^0, the second by 2^1 ... and (k + 1)th element by 2^k means multiplying [i + 1]th element by 2 and checking if it's greater than [i]th element. Check if nums[i] < 2 * nums[i + 1] if the above condition is satisfied widen the window and check if the window is greater than k, if the above condition failed to hold, start the search from the index that failed the condition.
Time Complexity O(n) Space Complexity O(1)
def inpNum(): return int(input()) def inpSepNum(): return map(int, input().split()) def inpNumList(): return list(map(int, input().split()))
test_cases = inpNum() for _ in range(test_cases):
n , k = inpSepNum() nums = inpNumList() subarrays = 0 left = 0 for right in range(1,n): # If the required condition failed move the left pointer to right if nums[right]*2 <= nums[right-1]: left = right # When the window size exceeds k increment subarrays if right - left >= k: subarrays += 1 print(subarrays)