Flipping Coins | CodeChef Solution

Hello coders, today we are going to solve Flipping Coins CodeChef Solution whose Problem Code is FLIPCOIN.

Task

There are N coins kept on the table, numbered from 0 to N – 1. Initially, each coin is kept tails up. You have to perform two types of operations:

1) Flip all coins numbered between A and B inclusive. This is represented by the command “0 A B”

2) Answer how many coins numbered between A and B inclusive are heads up. This is represented by the command “1 A B”.

Input Format

The first line contains two integers, N and Q. Each of the next Q lines are either of the form “0 A B” or “1 A B” as mentioned above.

Constraints

• 1 <= N <= 100000
• 1 <= Q <= 100000
• 0 <= A <= B <= N – 1

Output Format

Output 1 line for each of the queries of the form “1 A B” containing the required answer for the corresponding query.

Sample Input

4 7
1 0 3
0 1 2
1 0 1
1 0 0
0 0 3
1 0 3 
1 3 3

Sample Output

0
1
0
2
1

Solution – Flipping Coins

C++

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
ll seg[400010];
ll lazy[400010];
void up(int in,int l,int r,int sl,int sr)
{
    if(lazy[in]!=0)
    {
        seg[in]=(sr-sl+1)-seg[in];
        if(sl!=sr){
            lazy[2*in]=!lazy[2*in];
            lazy[2*in+1]=!lazy[2*in+1];
        }
        lazy[in]=0;
    }
    if(r<sl || l>sr || l>r)return;
    if(sl>=l && sr<=r)
    {
        seg[in]=(sr-sl+1)-seg[in];
        if(sl!=sr){
            lazy[2*in]=!lazy[2*in];
            lazy[2*in+1]=!lazy[2*in+1];
        }
        return;
    }
    int mid=sl+(sr-sl)/2;
    up(in*2,l,r,sl,mid);
    up(in*2+1,l,r,mid+1,sr);
    seg[in]=seg[in*2]+seg[in*2+1];
}
ll sum(int in,int l,int r,int sl,int sr)
{
    if(lazy[in]!=0)
    {
        seg[in]=(sr-sl+1)-seg[in];
        if(sl!=sr){
            lazy[2*in]=!lazy[2*in];
            lazy[2*in+1]=!lazy[2*in+1];
        }
        lazy[in]=0;
    }
    if(r<sl || l>sr || l>r)return 0;
    if(sl>=l && sr<=r)
     return seg[in];
    int mid=sl+(sr-sl)/2;
    return sum(in*2,l,r,sl,mid) + sum(in*2+1,l,r,mid+1,sr);
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,q;
    cin>>n>>q;
    while(q--)
    {
        int x,l,r;
        cin>>x>>l>>r;
        if(x==0)
        up(1,l,r,0,n-1);
        else{
            cout<<sum(1,l,r,0,n-1)<<"\n";
        }
    }
}

Python

import numpy as np

n,q = map(int,input().split())
List = np.zeros(n, dtype=bool)

for _ in range(q):
    one,l,r = map(int,input().split())
    
    if one:
        print(np.count_nonzero(List[l:r+1]))
    else:
        List[l:r+1] = ~List[l:r+1]

Java

/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
    private static class FastReader {
        BufferedReader reader;
        StringTokenizer st;

        public FastReader() {
            reader = new BufferedReader(new InputStreamReader(System.in));
        }

        public String next() throws Exception {
            if (st == null || !st.hasMoreElements()) {
                st = new StringTokenizer(reader.readLine());
            }
            return st.nextToken();
        }

        public Integer nextInt() throws Exception {
            return Integer.parseInt(next());
        }
    }
    
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		FastReader reader = new FastReader();
        int noOfCoins = reader.nextInt();
        int noOfQueries = reader.nextInt();

        BitSet bitSet = new BitSet(noOfCoins);
        StringBuilder result = new StringBuilder();

        for (int q = 0; q < noOfQueries; q++){
            int cmd = reader.nextInt();
            int A = reader.nextInt();
            int B = reader.nextInt();

            if (cmd == 0) {
                // Flip the coins
                bitSet.flip(A, B + 1);
            } else {
                // Count set bits between the range
                result.append("" + bitSet.get(A, B + 1).cardinality() + "\n");
            }
        }
        
        System.out.println(result.toString());
	}
}

Disclaimer: The above Problem (Flipping Coins) is generated by CodeChef but the Solution is Provided by CodingBroz. This tutorial is only for Educational and Learning Purpose.