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()

Let's see for each index $$$i$$$ among the permutation $$$p_n$$$ , what's the count of possible cases for it , we can use $$$(n-i)$$$ integers , thus for each index $$$i$$$ the count is $$$2^{n-i}$$$ , thus the answer will be the sum of count overall indices

due to exclusion of last index , complexity is $$$O(\log n)$$$ (Binary Exponentiation).

m=10**9+7
def p(a,b,m):
    a%=m
    r=1
    while(b>0):
        if(b&1):
            r=r*a%m
        a=a*a%m
        b>>=1
    return r
def ff(n):
    return (p(2,n,m)-n-1)%m
for _ in range(int(input())):
  n=int(input())
  print(ff(n))