Make a copy of the array $$$s$$$: call it $$$t$$$. Sort $$$t$$$ in non-decreasing order, so that $$$t_1$$$ is the maximum strength and $$$t_2$$$ — the second maximum strength.

Then for everyone but the best person, they should compare with the best person who has strength $$$t_1$$$. So for all $$$i$$$ such that $$$s_i≠t_1$$$, we should output $$$s_i−t_1$$$. Otherwise, output $$$s_i−t_2$$$ — the second highest strength, which is the next best person.

t = int(input())
for _ in range(t):
    n = int(input())
    s = list(map(int, input().split()))
    t = sorted(s)
    for i in range(n):
        if s[i] != t[-1]:
            s[i] = s[i] - t[-1]
        else:
            s[i] = s[i] - t[-2]
    print(*s)

We precalculate some array $$$A_{i}$$$, that $$$A_{i} = 1$$$, if $$$s_{i} = s_{i + 1}$$$, else $$$A_{i} = 0$$$. Now for any query ($$$l$$$, $r$), we need to find sum of $$$A_{i}$$$, such that $$$(l ≤ i < r)$$$. It has not become a range sum query problem. To solve this problem, we can precalculate a prefix sum array $$$Sum$$$, where $$$Sum_{i} = A_{1} + A_{2} + ... + A_{i}$$$. Then the sum of the interval ($$$l$$$, $$$r$$$) is $$$Sum_{r} — Sum_{l-1}$$$.

s = input()
m = int(input())
queries = []

for _ in range(m):
    queries.append(list(map(int, input().split())))

pref = [0]
for indx in range(len(s) - 1):
    if s[indx] == s[indx + 1]:
        pref.append(pref[-1] + 1)
    
    else:
        pref.append(pref[-1])


for left, right in queries:
    print(pref[right - 1] - pref[left - 1])

Sort the array in ascending order.

To solve this problem efficiently, we can use a sorting and greedy approach. Here's the step-by-step process:

1. Sort the given input array in ascending order.
2. It iterates through the sorted array. For each value, check if the current serving time is greater than the total waiting time of the current person (the sum of the previous satisfied customer's serving time ) . If it is, it means the person is satisfied. Otherwise, the person is not satisfied and will leave the queue automatically.

Time Complexity: O(n), n is the size of the queue.

Space Complexity: O(1)

    n = int(input())
    time = sorted(map(int, input().split()))

    ans = waitTime = 0
    for i in range(n):
        if waitTime <= time[i]:
            ans += 1
            waitTime += time[i]
    
    print(ans)

If there is at least a prefix or a suffix with non-positive sum, we can delete that prefix/suffix and end up with an array with sum $$$≥$$$ the sum of the whole array. So, if that's the case, the answer is "NO".

Otherwise, all the segments that Aman can choose will have a sum $$$<$$$ than the sum of the whole array because the elements that are not in the segment will always have a strictly positive sum. So, in that case, the answer is "YES".

Time complexity: O(n)

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    total_sum = 0
    for num in a:
        total_sum += num
        if total_sum <= 0:
            return False
    total_sum = 0
    for i in range(n - 1, -1, -1):
        total_sum += a[i]
        if total_sum <= 0:
            return False
    return True

T = int(input())
for _ in range(T):
    if solve():
        print("YES")
    else:
        print("NO")

Let's prove that for an array $$$a$$$ that was created by using a number of operations, with a sum of elements $$$s$$$ we can add into $$$a$$$ any number $$$x$$$ $$$(1≤x≤s)$$$.

Suppose that it is true that in the array $$$a$$$ with some length $$$l$$$ we introduce a number $$$x$$$ $$$(1≤x≤suma)$$$. Then after introducing we can create using the initial elements of the array any number $$$b$$$ $$$(1≤b≤suma)$$$ and using the element $$$x$$$ and some subset of the initial elements we can create any number $$$b$$$ $$$(x≤b≤suma+x)$$$, and because $$$x≤suma$$$ we proved that for the new array of length $$$l+1$$$ we can still create any number between $$$1$$$ and $$$suma+x$$$.

So we just need to verify if our array satisfies the above condition. We sort the array and check for every element whether the total sum so far is less than the current element. If that is the case for any of the elements our answer is ‘NO’ otherwise ‘YES’.

t = int(input())
for i in range(t):
    n = int(input())
    nums = list(map(int,input().split()))
    nums.sort()
    pos = 1
    if nums[0] != 1:
        pos = 0
    total = 1
    for i in range(1,n):
        if nums[i] > total:
            pos = 0
            break
        total += nums[i]
    if pos:
        print("YES")
    else:
        print("NO")

How would you solve count subarrays with sum equal to $$$k$$$ optimally using the concept of prefix sum?

We will keep track of the prefix product.

Lets call the current prefix product $$$currentPrefix$$$.
If $$$currentPrefix$$$ is positive,

1. If we have seen another positive prefix before, it means that the segment of the currentPrefix excluding the previous prefix would give us a positive product, because $$$(+)*(+) = (+)$$$. The amount of previous positive prefixes tells us how many segments with positive product we can have at the current prefix.
2. Similarly, if we have seen a negative prefix before, it means that the remaining part of the current segment has to be negative, because $$$(-)*(-) = (+)$$$.

In the same manner, if $$$currentPrefix$$$ is negative,

1. We increment the negative product segments by the number of previous positive prefixes, because $$$(+)*(-) = (-)$$$.
2. We increment the positive product segments by the number of previous negative prefixes, because $$$(-)*(+) = (-)$$$.

n = int(input())
a = list(map(int, input().split()))

pos_prefixes = 1 # as an identity, to take into account a whole prefix
neg_prefixes = 0

pos_seg_count = 0
neg_seg_count = 0

prefix = 1

for num in a:
    prefix *= (num//abs(num)) # we only want the sign, not the magnitude

    if prefix > 0:
        pos_seg_count += pos_prefixes
        neg_seg_count += neg_prefixes
        pos_prefixes += 1
        
    else:
        pos_seg_count += neg_prefixes
        neg_seg_count += pos_prefixes
        neg_prefixes += 1

print(neg_seg_count, pos_seg_count)