Home Arrays [Hackerrank] – Birthday Cake Candles Solution

[Hackerrank] – Birthday Cake Candles Solution

by nikoo28
0 comment

Question: You need to count the number of tallest candles on the cake.

Input: candles = [4, 4, 1, 3]

Output: 2

Let us try to understand the problem statement and its test case first.

You are in charge of candles on a birthday cake for a child. However, the child can only blow out the tallest candles. There could be one or more candles on the cake that are tallest. Hence, you need to return the number of tallest candles you can find.

Let us take a sample test case. candles[ ] = [3, 2, 1, 3]. Here the integers in the array represent the height of each of the candle. They are placed on the cake something like the image shown below.

Image showing birthday cake candles
Fig: Sample test case

You can see that some candles are small and some are large. If you look closely, the tallest candle available here is of the length 3 and there are 2 of such candles. According to the question, when you blow out, only the tallest candles extinguish. If you blow, your cake looks like this now.

Image showing blown out candles
Fig: Tallest candles blown out

In this test case, 2 candles are blown out. Hence, 2 is the answer.

Method 1:

This is a very simple problem to solve, if you don’t apply too much complications. A very basic algorithm will be something like:

  • Iterate through the array and find the length of the tallest candle.
  • Store this length.
  • Go over the array once again and check if the candle matches the maximum length.
  • If yes, increment a result counter. Else, continue to the next candle.
  • Return the result.

Quite a straight forward approach. Let us assume that we have a sample array:
candles[] = [4, 1, 1, 4, 3, 4]

sample test case
Fig: Sample array

This can represent the birthday cake candles:

Image showing representation of birthday cake candles with array
Fig: Candles represented by array

On doing one iteration, we find that the largest value in the array is 4. In the next iteration, we compare each value in the array to the maximum value and if they match, increment a counter. At the end, we get the total number of blown out candles to be 3.

image showing 3 blown out candles
Fig: 3 candles blown out

Code:

int birthdayCakeCandles(List<Integer> candles) { int maximum = Integer.MIN_VALUE; // Get the height of the tallest candle for (Integer candle : candles) { if (candle >= maximum) maximum = candle; } // Count how many tallest candles are present int result = 0; for (Integer candle : candles) { if (candle == maximum) result++; } return result; }
Code language: Java (java)

Time Complexity: O(n)
Space Complexity: O(1)

Method 2: Using single iteration (stream of numbers)

You don’t really need to scan the array 2 times, to determine the tallest birthday cake candles. This problem can be actually converted to determine the count of largest numbers in a stream of integers.

The basic algorithm would be:

  • Consider first number to be the largest number and set counter = 1.
  • If the next number is smaller than the largest number, continue.
  • If the next number is same as the largest number, increment the counter by 1
  • However, if the next number is larger than the largest number, reset the counter to 1, and change the largest number to this new number.
  • Keep repeating the above 3 steps until you are getting a stream of numbers.
  • Return the counter at the end.

Code:

int birthdayCakeCandlesStream(List<Integer> candles) { int maximum = Integer.MIN_VALUE; int result = 0; for (Integer candle : candles) { if (candle < maximum) continue; if (candle == maximum) result++; if (candle > maximum) { result = 1; maximum = candle; } } return result; }
Code language: Java (java)

Video Explanation:

0 comment

You may also like

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More