Problem solving with programming: Birthday candles - Codechef problem

Problem solving with programming: Birthday candles - Codechef problem

A number of candles are given each of them labelled with the digit 0-9. We have to find the minimum positive number that can not be formed with the given candles. 

The input is given as an array of size 10.
Array[0] indicates the number of '0' candles
Array[1] indicates the number of '1' candles and so on upto Array[9].

• Identify the left most digit with minimum count. It can be '0' also.

• Form a number by repeating the minimum digit  (count+1) times

• A special case occurs when '0' candle has minimum count, we have to prefix '1' to it, as we can not have all zeros.

• One more special case is when 0 and some other digit has the same minimum count, we have to consider the left most non-zero digit. Take a look at the following case to understand the situation. 
• 2  3  4   7  6  2  8  3  5  9
• Both '0' and '5' has the count of 2. If we consider zero, the output becomes 1000 according to the above algorithm. If we consider '5', the output becomes 555. Since 555 < 1000; the answer should be 555.

string getSmallest()


{


 int i; 


 //Find the min count among dCount[1..9]


 int mCount = dCount[1], mDigit = 1;


 


 for( i = 2; i < 10; i++ )


 {


  if( mCount > dCount[i] )


  {


   mCount = dCount[i];


   mDigit = i;


  }


 }


 //If 0 has minimum count, update mCount and mDigit


 if( mCount > dCount[0] )


 {


  mCount = dCount[0];


  mDigit = 0;


 }


 


 stringstream ss;


 string result;


 


 for( i = 0; i <= mCount; i++ )


  ss << mDigit;


 


 if( mDigit == 0 )


  result = "1" + ss.str();


 else


  result = ss.str();


 


 return result;


}

Read full article from Problem solving with programming: Birthday candles - Codechef problem