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

the given condition is $$$x \le i \le j \le y$$$, which implies $$$i \le j$$$, meaning we don't have to consider elements with $$$i > j$$$, and can set to $$$0$$$. Now, what if we find sum of $$$g[i][j]$$$, such that $$$x \le i, j \le y$$$ , The indices which do not satisfy $$$i \le j$$$ are set to $$$0$$$, meaning that it doesn't affect the answer. Thus, it's enough to output the sum of integers of the new grid's sub-grid $$$(x, x)$$$ to $$$(y, y)$$$ per query, which can be done using 2d prefix sum.

Let's say $$$x=0$$$ for all the queries. Then, we can sort all the queries by $$$y$$$, and setup a segment tree(XOR). From the smallest $$$y$$$, we check all integers in the array which are $$$\le y$$$, and update them in segment tree. Now, for each query it's simple range XOR query on segtree.

What if that's not the case, and $$$x > 0$$$ ? Then the answer for query l r x y is (l r 0 x-1) ^ (l r 0 y), both of which can be processed using the method above. At most, he have to process $$$2q$$$ queries of type l r 0 y

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

can be done with simple Treap, or using offline queries and an ordered set / segtree and array recovery with answering/handling queries in reverse, or sqrt decomposition.

simple centroid decomposition problem, precomputing the answers for each centroid using prefix sums and answering the queries in $$$O(\log n)$$$ or $$$O(\log^2 n)$$$ depending on the implementation, and using the fact that $$$q(l, r) = q(1, r) - q(1, l-1)$$$.