Please help me optimize this code

[neil_mahaseth]

There are N coins kept on the table, numbered from 0 to N - 1. Initally, each coin is kept tails up. You have to perform two types of operations :
1) Flip all coins numbered between A and B. This is represented by the command "0 A B"
2) Answer how many coins numbered between A and B are heads up. This is represented by the command "1 A B".
Input :
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.
Output :
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

#include<iostream>

int main()
{

	unsigned int N,Q,temp,op,A,B,count;
	scanf ("%u%u",&N,&Q);
    bool *coin=new bool [N];
	for(temp=0;temp<N;temp++)
	coin[temp]=true;
 	for(int temp1=0;temp1<Q;temp1++)
	{
		count=0;
		scanf ("%u%u%u",&op,&A,&B);
		
		switch(op)
		{
		 case 0:
			 for(temp=A;temp<=B;temp++)
			 {
	           if(coin[temp]==true)
				 coin[temp]=false;
			   else
				 coin[temp]=true;
			 }
			 break;
			    
         case 1:
			 for(temp=A;temp<=B;temp++)
			 {
	            if(coin[temp]==false)
				count++;

			 }
			 printf ("\n%u\n",count);
			 break;
         default:
			 break;

		}
	
	}

	delete coin;
	return 0;
}

The following code gives the correct output but it is very slow please help me suggesting a different algorithmic thank you in advance.

[Agni]

Have you tried looking at bitwise operators? See if you can use bitset class, representing each position as a bit with 0 representing OFF and 1 representing ON

[Andreas5]

if(coin[temp]==true)
				 coin[temp]=false;
			   else
				 coin[temp]=true;

Can be replaced with

coin[temp] = !coin[temp]

Atleast thats something :P

[neil_mahaseth]

Have you tried looking at bitwise operators? See if you can use bitset class, representing each position as a bit with 0 representing OFF and 1 representing ON

Thanks for responding.But i had doubt can we allocate memory two bitset operator dynamically because the value of N(number of coins) can vary from 1 to 100000.It would be more helpful if some one suggests an algorithm that dose not depends on the number coins.

[vijayan121]

Use std::vector<bool> for space efficiency (if N is large).
And std::transform and std::count for programmer efficiency.

#include <iostream>
#include <vector>
#include <functional>

int main()
{
    const bool TAIL = false, HEAD = true ;
    enum { FLIP_THEM = 0, COUNT_HEADS = 1 } ;

    std::vector<bool>::size_type N, Q ;
    std::cin >> N >> Q ;

    std::vector<bool> coins( N, TAIL ) ;
    std::vector<bool>::iterator begin = coins.begin() ;

    int command ;
    std::vector<int>::size_type pos_from, pos_upto ;

    while( ( Q-- > 0 ) && ( std::cin >> command >> pos_from >> pos_upto ) )
    {
        if( command == FLIP_THEM )
           std::transform( begin+pos_from, begin+pos_upto+1,
                           begin+pos_from, std::logical_not<bool>() ) ;

        else if( command == COUNT_HEADS )
           std::cout << std::count( begin+pos_from, begin+pos_upto+1,
                                    HEAD ) << '\n' ;
    }
}

[tajendra]

I have removed your cost of calculating coins head up count totally, just have a look at it. Introduced one new variable nFalseCoinCount , to your code. It will account all your coins heads up count.:icon_biggrin:

#include<iostream>

int main()
{

	unsigned int N,Q,temp,op,A,B,count;
	scanf ("%u%u",&N,&Q);
    bool *coin=new bool [N];
	for(temp=0;temp<N;temp++)
	coin[temp]=true;
	unsigned int nFalseCoinCount = 0;
 	for(int temp1=0;temp1<Q;temp1++)
	{
		count=0;
		scanf ("%u%u%u",&op,&A,&B);
		
		switch(op)
		{
		 case 0:
			 {
				 nFalseCoinCount = 0;
				 for(temp=A;temp<=B;temp++)
				 {
					 if(coin[temp]==true)
					 {
						 coin[temp]=false;
						 nFalseCoinCount++;//counting at time of flipping
					 }
					 else
					 {
						 coin[temp]=true;
					 }
				 }
			 }
			 break;
			    
         case 1:
			 //No need to calculate every time here;
			 /*for(temp=A;temp<=B;temp++)
			 {
	            if(coin[temp]==false)
				count++;

			 }
			 */
			 printf ("\n%u\n",nFalseCoinCount);
			 break;
         default:
			 break;

		}
	
	}

	delete coin;
	return 0;
}

[Aranarth]

@tajendra
Note that the coin counting must work for arbitrary coin ranges, not just the entire range.
Also, you need to reduce nFalseCoinCount when appropriate.

If vijayan121's solution is not fast enough (you're already compiling with -O3, right?), you can implement vector<bool>'s shifting logic yourself and then flip 32/64/128 coins at a time (for 32/64 bit and SSE2 targets, respectively).

For fast population count (=tails up counting), see:
http://gurmeetsingh.wordpress.com/2008/08/05/fast-bit-counting-routines/
http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive
http://cage.ugent.be/~klein/popcnt.web

and the POPCNT SSE4(a) instruction for CPU targets that support it.

[neil_mahaseth]

I have removed your cost of calculating coins head up count totally, just have a look at it. Introduced one new variable nFalseCoinCount , to your code. It will account all your coins heads up count.:icon_biggrin:

#include<iostream>

int main()
{

	unsigned int N,Q,temp,op,A,B,count;
	scanf ("%u%u",&N,&Q);
    bool *coin=new bool [N];
	for(temp=0;temp<N;temp++)
	coin[temp]=true;
	unsigned int nFalseCoinCount = 0;
 	for(int temp1=0;temp1<Q;temp1++)
	{
		count=0;
		scanf ("%u%u%u",&op,&A,&B);
		
		switch(op)
		{
		 case 0:
			 {
				 nFalseCoinCount = 0;
				 for(temp=A;temp<=B;temp++)
				 {
					 if(coin[temp]==true)
					 {
						 coin[temp]=false;
						 nFalseCoinCount++;//counting at time of flipping
					 }
					 else
					 {
						 coin[temp]=true;
					 }
				 }
			 }
			 break;
			    
         case 1:
			 //No need to calculate every time here;
			 /*for(temp=A;temp<=B;temp++)
			 {
	            if(coin[temp]==false)
				count++;

			 }
			 */
			 printf ("\n%u\n",nFalseCoinCount);
			 break;
         default:
			 break;

		}
	
	}

	delete coin;
	return 0;
}

The Following code is not correct as the value of A & B while flipping & counting the tails are different.But any way thanks for responding.