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

notice that the set of prime factors common between numerator and denumerator are the same and in the numerator for each power of common it’s at least has the same power as den and We’re aiming to minimize the product thus we need to make a divisible by b (for each prime separately) so whenever we had an even power for some prime the best thing is split it into equal parts.

Calculate sieve for all numbers upto $$$2 \cdot 10^5$$$ this can be achieved in $$$O(n \log(\log(n)))$$$ which is fast , Find the prime factorization of $$$n!$$$ this can be found with the prime factorization form of $$$n!$$$

For each prime factor $$$p_i$$$ the power $$$\alpha_i$$$ can be calculated with the following formula

it can be show that this sum converges in $$$a$$$ , $$$O(\log(n))$$$ it’ll take no more than $$$20$$$ runs , thus the final prime factorization will take $$$O(20p)$$$.

Now we want to have $$$a \bmod b = 0$$$ (assuming fraction $$$\frac{a}{b}$$$) , so a productive greedy is to have for each $$$p_i$$$ with power $$$\alpha_i$$$ the following : for $$$a$$$ the power is $$$\displaystyle \left \lceil \frac{\alpha_i}{2} \right \rceil$$$ and for $$$b$$$ the power is $$$\displaystyle \left \lfloor \frac{\alpha_i}{2} \right \rfloor$$$.

Therefore we only need to look at $$$\alpha_i \bmod 2 = 1$$$ i.e. odd powers , and calculate The following

For each test case , we calculate for each prime upto $$$n$$$ it’s power , the count of prime upto $$$n$$$ are approximately $$$O \left ( \frac{n}{\log(n)} \right )$$$ and we check the power in $$$O(\log(n))$$$ and even better in practice , this yields prime factorization of $$$n!$$$ takes at most $$$O(n)$$$ time , we can with each prime factorized if the final power is odd then multiply it by the answer and take the modulus by $$$10^9 + 7$$$ , thus the total complexity for multiple test cases is $$$O(8 \cdot 10^5)$$$ for precalculation of sieve (primes) , and $$$O(\sum n)$$$ for answering test cases.

def solve():
    x = int(input())
    ip= [1] * (x + 1)
    ip[0] = ip[1] = 0
    for i in range(2, int(x**0.5) + 1):
        if ip[i]:
            for j in range(i * i, x + 1, i):
                ip[j] = 0
    p = [0] * (x + 1)
    for i in range(2, x + 1):
        if ip[i]:
            cnt = 0
            j = i
            while j <= x:
                cnt += x // j
                if j > x // i: break
                j *= i
            p[i] = cnt
    ans = 1
    MOD = 10**9 + 7
    for i in range(2, x + 1):
        if p[i] % 2:
            ans = (ans * i) % MOD
    print(ans)

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