Since only entries in array are binary digits, all 0s must be before 1s. So we can use two pointers to interchange 0s to 1s and count the operations. The maintain 2 pointers the left pointer will be looking for the first 1 and the right pointer will be looking for the first 0. if they both don't cross each other, then simply replace. loop ends if left pointer becomes greater than right pointer or they become equal.

// Aur Bhai Dekhne aagaye ;)
// Author: Abhijit Mishra 
#include <bits/stdc++.h>
using namespace std;


#define nl cout << "\n"
#define all(x) x.begin(), x.end()
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);


typedef long long int ll;
typedef vector<ll> vi;


int main()
{
    fast;
    ll t = 1;
    cin >> t;
    while (t--)
    {
        ll n;
        cin >> n;
        vi a(n);
        for (int i = 0; i < n; i++)
        {
            cin >> a[i];
        }

        if (is_sorted(all(a))) { cout << 0; }
        else
        {
            ll ans = 0;
            ll l = 0, r = n - 1;
            while (l != r)
            {
                if (a[l] == 0) { l++; }
                else if (a[r] == 1) { r--; }
                else if (a[l] == 1 && a[r] == 0)
                {
                    a[l] = 0;
                    a[r] = 1;
                    ans++;
                }
            }
            if (is_sorted(all(a))) { cout << ans; }
        }
        nl;

    }
    return 0;
}

import java.util.*;


public class Rebellion {
	public static void main(String[]args){

        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while(t>0){
            int n = sc.nextInt();
            int[] arr = new int[n];
            for(int i = 0;i<n;i++) arr[i] = sc.nextInt();
            int p1 = 0;
            int p2 = n-1;
            int ans = 0;
            while(p1<p2){
                if(arr[p1] == 0){
                    p1++;
                    continue;
                }
                if(arr[p2] == 1){
                    p2--;
                    continue;
                }
                if(arr[p1] ==  1 && arr[p2] ==  0){
                    ans++;
                    p1++;
                    p2--;
                }
            }
            System.out.println(ans);
            t--;
        }
	}
}

There are 2 approaches to solve this problem.

DataStructure approach

We use a dequeue, it stands for a double ended queue. Use it to keep on removing the first or last element and maintain to variables for each of the player. repeat this process till the deque is empty.

2 pointer approach

Same as the above approach instead of the data structure, we just keep to pointers at the start and the end and do the same process.

// Aur Bhai Dekhne aagaye ;)
// Author: Abhijit Mishra 
#include <bits/stdc++.h>
using namespace std;


#define nl cout << "\n"
#define all(x) x.begin(), x.end()
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);


typedef long long int ll;
typedef vector<ll> vi;


int main()
{
    fast;
    ll n;
    cin >> n;
    deque<ll> a(n);
    for (int i = 0; i < n; i++) { cin >> a[i]; }
    ll one = 0, two = 0;
    while (!a.empty())
    {
        if (a.front() > a.back())
        {
            one += a.front();
            a.pop_front();
        }
        else
        {
            one += a.back();
            a.pop_back();
        }
        if (!a.empty())
        {
            if (a.front() > a.back())
            {
                two += a.front();
                a.pop_front();
            }
            else
            {
                two += a.back();
                a.pop_back();
            }
        }

    }
    cout << one << " " << two;
    nl;

    return 0;
}

```

```

4 hours = 240 minutes
time taken to get the party = x
so, 240-x is the time we have for solving problems.

// Aur Bhai Dekhne aagaye ;)
// Author: Abhijit Mishra 
#include <bits/stdc++.h>
using namespace std;


#define nl cout << "\n"
#define all(x) x.begin(), x.end()
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);


typedef long long int ll;
typedef vector<ll> vi;


int main()
{
    fast;
    ll n, k;
    cin >> n >> k;
    int x = (240 - k);
    ll ans = -1;
    for (int i = 1; i <= n; i++)
    {
        if (x >= 5 * i)
        {
            x -= 5 * i;
            ans = i;
        }
        else { break; }
    }
    cout << ans;
    nl;
    return 0;
}

Sort the array. Perform binary search and look for the query. Look for the upper bound in the query. Print the index for every query.

// Aur Bhai Dekhne aagaye ;)
// Author: Abhijit Mishra 
#include <bits/stdc++.h>
using namespace std;

#define nl cout << "\n"
#define all(x) x.begin(), x.end()
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

typedef long long int ll;
typedef vector<ll> vi;

int main()
{
    fast;

    ll n;
    cin >> n;
    vi a(n);
    for (int i = 0; i < n; i++) { cin >> a[i]; }
    sort(all(a));
    ll q;
    cin >> q;

    while (q--)
    {
        ll k;
        cin >> k;
        cout << upper_bound(all(a), k) - a.begin();
        nl;
    }

    return 0;
}

```

```

if a's value is fixed then b = cuberootof(x³ — a³)
we can create a list containing all the cubes of values from 1 to 10000. Then take values from this list and subtract it from x³. then perform binary search in this list since it contains all the cubes our value of b must be present in the list.

// Aur Bhai Dekhne aagaye ;)
// Author: Abhijit Mishra 
#include <bits/stdc++.h>
using namespace std;


#define nl cout << "\n"
#define all(x) x.begin(), x.end()
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);


typedef long long int ll;
typedef vector<ll> vi;

int main()
{
    fast;
    ll t = 1;
    cin >> t;
    while (t--)
    {
        ll n;
        cin >> n;
        vi a(10000);
        for (long long i = 1; i < 10000; i++)
        {
            a[i] = i * i * i;
        }
        bool ok = false;
        ll i = 0;
        if (binary_search(all(a), n)) { cout << "NO"; }
        else
        {
            while (!ok && i < 9999)
            {
                ll temp = n - a[i];
                ok = binary_search(all(a), temp);
                i++;
            }
            if (ok) { cout << "YES"; }
            else { cout << "NO"; }
        }nl;

    }
    return 0;
}

```

```

We simply initialize an array with the first element always equal to zero, because if the size of the string is 1 then there will be index satisfying s[i] = s[i+1].
then simply iterate over the string if the char is equal to the previous char then increment the previous arr value and store it in the current position. This is the prefix sum method, since we are calculating the values of all the prefix one by one.
s = ..#...#
prefixarr = [0,1,1,1,2,3,3]
if the query is 2,4 . our ans will be prefixarr[4] — prefixarr[2]
This is a very powerful techniques so solving problems and quiet often asked in job interviews and low rated contest.

// Aur Bhai Dekhne aagaye ;)
// Author: Abhijit Mishra 
#include <bits/stdc++.h>
using namespace std;


#define nl cout << "\n"
#define all(x) x.begin(), x.end()
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);


typedef long long int ll;
typedef vector<ll> vi;

int main()
{
    fast;
    string s;
    cin >> s;
    ll z = s.length();
    vi a(z);
    for (int i = 0; i < z; i++)
    {
        if (i == 0) { a[i] = 0; }
        else if (s[i] == s[i - 1]) { a[i] = a[i - 1] + 1; }
        else { a[i] = a[i - 1]; }
    }
    ll n;
    cin >> n;
    while (n--)
    {
        ll x, y;
        cin >> x >> y;
        cout << a[y - 1] - a[x - 1];
        nl;
    }
    return 0;
}

```

```

Fact: Low rated problems with queries are mostly solved via prefix sum. (sometimes via dynamic programming , segment trees, etc)

Sort sequence v to obtain sequence u.
Sorting can be done in using quicksort O(n log (n))
Now we are interested in the sum of a interval of a given sequence.
This can be done by calculating the prefix sum of the sequence beforehand.

Preprocessing takes O(n) time, and answering a query is only O(1). The total complexity would be .

// Aur Bhai Dekhne aagaye ;)
// Author: Abhijit Mishra 
#include <bits/stdc++.h>
using namespace std;


#define nl cout << "\n"
#define all(x) x.begin(), x.end()
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);


typedef long long int ll;
typedef vector<ll> vi;

int main()
{
    fast;
    ll n;
    cin >> n;
    vi a(n);
    vi prea(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        if (i != 0)
        {
            prea[i] = a[i] + prea[i - 1];
        }
        else
        {
            prea[0] = a[0];
        }
    }


    vi b = a;
    sort(all(b));
    vi preb(n);
    preb[0] = b[0];
    for (int i = 0; i < n; i++)
    {
        if (i != 0)
            preb[i] = b[i] + preb[i - 1];
    }

    ll q;
    cin >> q;
    while (q--)
    {
        ll x, y, z;
        cin >> x >> y >> z;

        if (x == 1)
        {
            cout << prea[z - 1] - prea[y - 1] + a[y - 1];
            nl;
        }
        else if (x == 2)
        {
            cout << preb[z - 1] - preb[y - 1] + b[y - 1];
            nl;
        }
    }
    return 0;
}

```

```

The problem can be divided into two classic ones:

1.Count the number of pairs ai+aj≤r;
2.Count the number of pairs ai+aj≤l−1.

Now it might be obvious to use prefix sum.

Let A — be the answer to the first problem, and B — be the answer to the second problem. Then A−B
is the answer to the original problem.
The new problem can be solved by binary search. Iterate over the first element of the pair. Then you need to count the number of elements such that aj≤r−ai. If you sort the array, this value can be calculated by running a single binary search.

// Aur Bhai Dekhne aagaye ;)
// Author: Abhijit Mishra 
#include <bits/stdc++.h>
using namespace std;


#define nl cout << "\n"
#define all(x) x.begin(), x.end()
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);


typedef long long int ll;
typedef vector<ll> vi;

int main()
{
    fast;
    ll t = 1;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        vector<int> cnt(n + 1);
        for (int i = 0; i < n; ++i)
        {
            int x;
            cin >> x;
            ++cnt[x];
        }
        int ans = 0;
        for (int s = 2; s <= 2 * n; ++s)
        {
            int cur = 0;
            for (int i = 1; i < (s + 1) / 2; ++i)
            {
                if (s - i > n) continue;
                cur += min(cnt[i], cnt[s - i]);
            }
            if (s % 2 == 0) cur += cnt[s / 2] / 2;
            ans = max(ans, cur);
        }
        cout << ans << endl;
    }
    return 0;
}

```

```

Refer to Problem C on link. Explained beautifully by BledDest

// Aur Bhai Dekhne aagaye ;)
// Author: Abhijit Mishra 
#include <bits/stdc++.h>
using namespace std;


#define nl cout << "\n"
#define all(x) x.begin(), x.end()
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);


typedef long long int ll;
typedef vector<ll> vi;

int main()
{
    fast;
    ll t = 1;
    cin >> t;
    while (t--)
    {
        ll n;
        cin >> n;

        vi a(n), b(n);
        vi c(n), d(n);
        vi x(n);
        for (int i = 0; i < n; i++) { cin >> a[i]; }
        for (int i = 0; i < n; i++) { cin >> b[i]; }
        ll j = 0;
        for (int i = 0; i < n; i++)
        {
            while (b[j] < a[i])
            {
                j++;
            }
            if (b[j] > a[i])
            {
                c[i] = b[j] - a[i];
            }
        }

        x[n - 1] = b[n - 1];
        for (int i = n - 1; i >= 0; i--)
        {
            if (b[i] >= a[i + 1])
            {
                if (i == n - 2)
                {
                    x[i] = b[i + 1];
                }
                else
                {
                    x[i] = x[i + 1];
                }
            }
            else
            {
                x[i] = b[i];
            }
        }

        for (int i = 0; i < n; i++)
        {
            d[i] = x[i] - a[i];
        }
        for (int i = 0; i < n; i++)
        {
            cout << c[i] << " ";
        }
        nl;
        for (int i = 0; i < n; i++)
        {
            cout << d[i] << " ";
        }
        nl;
    }
    return 0;
}

```

```