Connection Status:
Competition Arena > OlympicCandles

OlympicCandles

SRM 408 · 2008-07-01 · by connect4

SRM 408 · 2008-07-01 · by connect4 · Greedy
Class Name: OlympicCandles
Return Type: int
Method Name: numberOfNights
Arg Types: (vector<int>)
Problem Statement

Problem Statement

To celebrate the upcoming Thought Challenge Olympics, you are going to follow tradition and light candles. On the first night of the event, you will light one candle. At the end of the night, you will extinguish the candle. On each subsequent night, you will light one more candle than you did on the previous night, so that on the n-th night (indexed from 1) you will light n candles (and extinguish them all in the morning). Each night that you light a candle, its height will decrease by 1 inch; once its height reaches 0 inches, you cannot use it anymore.

You are given a int[] candles, the i-th element of which is the height of the i-th candle that you own. Return the maximum number of nights you can celebrate the event without going to the store to get more candles. For example, if you have three candles of height 2, you can light one the first night, the other two on the second night, and then all three candles on the third night.

Constraints

  • candles will contain between 1 and 50 elements, inclusive.
  • Each element of candles will be between 1 and 100, inclusive.
Examples
0)
{2, 2, 2}
Returns: 3

The example from the statement.

1)
{2, 2, 2, 4}
Returns: 4

With an extra candle we are able to use the candles for four nights.

2)
{5, 2, 2, 1}
Returns: 3
3)
{1, 2, 3, 4, 5, 6}
Returns: 6
4)
{4, 5, 2}
Returns: 3

Submissions are judged against all 88 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class OlympicCandles with a public method int numberOfNights(vector<int> candles) · 88 test cases · 2 s / 256 MB per case

Submitting as anonymous