We can obtain $$$n$$$ from the binary representation as following

We know that the fact

Let’s consider the last active bit i.e. $$$\mathtt{1}$$$ is $$$i$$$ then $$$n$$$ as integer is

thus the answer is the index of last occurrence of $$$\mathtt{1}$$$ , Complexity $$$O(n)$$$.

for _ in range(int(input())):
    n=int(input())
    s=input()
    ans=0
    for i in range(n):
        if(s[i]=='1'):
            ans=n-i-1
            break
    print(ans)

Maintain two arrays $$$b$$$ and $$$c$$$ such that

Now , maintain a function $$$f$$$ that process the maximum subarray sum in $$$O(n)$$$ for both of arrays $$$b$$$ and $$$c$$$ (Kadane's Algorithm for example), be careful of initialization that it’s non-empty , and the answer is $$$\max(f(b),f(c))$$$ , Complexity $$$O(n)$$$.

def f(a):
    best = a[0]  
    sum = a[0]   
    for i in range(1, len(a)): 
        sum = max(a[i], sum + a[i])
        best = max(best, sum)
    return best

for _ in range(int(input())):
    n, k = list(map(int, input().split()))
    a = list(map(int, input().split()))
    b = a.copy()
    c = a.copy()
    for i in range(n):
        b[i] //= k
        c[i] *= k
    print(max(f(b), f(c)))

One way to solve the problem is to make a fixed-size sub-array and iterate through the array and test all the subarrays with length $$$k$$$ i.e Sliding window of length $$$k$$$ , so we can make a sliding window with length $$$k$$$ and iterate the array which yields $$$n- k + 1$$$ and you delete $$$k − 1$$$ elements in total then the total complexity for each case can reach $$$O(n^2)$$$ ,Unfortunately it’s not efficient enough so we should optimize!. We can optimize the solution by making a frequency map ; we use a greedy approach by removing the first $$$k$$$ elements from Map (dict) structure , and then doing a sliding window minimum and finally obtain the minimum final number of distinct numbers , total complexity is $$$O(n \log n)$$$ due to using maps.

def solve(): n,k = map(int,input().split()) a = list(map(int,input().split())) a = [str(arr[i]) for i in range(n)] dic = {} for num in a: if num not in dic: dic[num] = 0 dic[num] += 1 for i in range(k): dic[a[i]] -= 1 if dic[a[i]]==0: del dic[a[i]] ans = len(dic) for i in range(k,n): if a[i-k] not in dic: dic[a[i-k]] = 0 dic[a[i-k]] += 1 dic[a[i]] -= 1 if dic[a[i]]==0: del dic[a[i]] ans = min(ans, len(dic)) print(ans)

for _ in range(int(input())): solve()