We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Practice
  2. Algorithms
  3. Warmup
  4. Birthday Cake Candles
  5. Discussions

Birthday Cake Candles

  • jord_fumar + 4 comments

    Be aware of time complexity. In my testcase 4, n was 10000. If you use a sorting algorithm with n^2, you will get a runtime error.

    The way I structured my code is:

    1. Sort the array from min to max (quickSort)
    2. Parse from the very end of the array and iterate count++.
    3. When your values are no longer identical, stop.
    • jagmeetsingh + 8 comments

      I tried this

      static int birthdayCakeCandles(int[] a) {
        Arrays.sort(a);  //double pivot QuicKSort
        int count = 0;
        int i = a.length - 1;
        int tallest = a[i];
        while (a[i--] == tallest) {
            count++;
        }
        return count;
    }

      It is failing the test case

      100000 followed by 100000 times 9999999 (as height of candles(array values)).

      • x_ireesh_x + 0 comments

        Pass all Testcases..

        static int birthdayCakeCandles(int[] ar) {
    Arrays.sort(ar);
    int result = 1;
    int decriment = 2;
    while((decriment <= ar.length) && (ar[ar.length-1] == ar[ar.length-decriment])){
        result++;
        decriment++;
    }
    return result;
}
      • rishavtandon93 + 1 comment

        Try This

        static int birthdayCakeCandles(int[] ar) {

            int count =0;
    Arrays.sort(ar);
    int maxHeight = ar[(ar.length)-1];
    for(int i=0;i<ar.length;i++)
    {
        if(ar[i]==maxHeight)
        {
            count++;
        }
    }

    return count;

}
        • Kanahaiya + 2 comments

          Hi,

          Your solution is good but it will take O(nlogn) time due to sorting which can be optimized to O(n)

          Here is the video explanation of my solution in O(n) time -

          https://youtu.be/1gxFE9EfanE

          Any comments and feedback will be appreciated.

          • wdodman + 1 comment

            Thanks for that. I worked out a solution where I do it in O(n) time. Posted on your video.

            • Kanahaiya + 0 comments

              most welcome. :)

              If you dont mind can you please provide a feedback on my video by commenting or liking & disliking. It will help me and others too to find the solution over internet.

          • munnidivya93 + 2 comments

            thanks

            • Kanahaiya + 0 comments

              most welcome. :)

              If you dont mind can you please provide a feedback on my video by commenting or liking & disliking. It will help me and others too to find the solution over internet.

            • Kanahaiya + 0 comments
              [deleted]
      • Amit_Sharma + 0 comments

        need to add one more check in while condition for all the array elements with same value

        while ( i > -1 && a[i--] == tallest ) { count++; }

      • dpkcareergreatn1 + 0 comments

        Count should be initialized to 1 as there is atleast one tallest. In this case, if the frequency of largest element is 0, count would return 0 which is an error

      • wdodman + 1 comment

        Mine fails on that too. ar.sort(); ar.reverse(); let m = 0; let k = ar[0]; while (parseInt(ar[m]) === parseInt(k)){ m++; } return m; }

        • Kanahaiya + 0 comments

          Hi,

          Here is the video explanation of my solution in O(n) time -

          https://youtu.be/1gxFE9EfanE

          Any comments and feedback will be appreciated.

      • harikrishnaprak1 + 0 comments

        while (i>-1&&a[i--] == tallest) { count++; }

        You just forgot to check whether the index i is within the bounds.

      • pbpraveen1988 + 0 comments

        Same issue with that case for me as well in javascript

      • arorashivam + 0 comments

        ar_count = int(raw_input())

        ar = list(map(int, raw_input().strip().split()))

        max_height = max(ar)

        print(ar_count - len(list(filter(lambda x: x!=max_height,ar))))) Try this! It worked when I split max into a different line.

    • bertgayus + 1 comment

      if you use quicksort u already have O(nlogn) which is worse than just iteratring through the array and saving the highest value and then just iterate a second time incrementing a counter everytime the value is similar to the saaved one. then complexity is O(2n) = O(n). With n = 100 you would have ~ 600 steps(n*logn = 100 * 6 = 600) with your solution and just 200 steps with mine

      • Alex_Marble + 1 comment

        Wouldn't it be faster to maintain your count in the initial iteration? 

        
    static int birthdayCakeCandles(int[] ar) {
        int height = ar[0];
        int count = 1;
        for (int i = 1; i < ar.Count();i++)
        {
            if (ar[i] > height){
                height = ar[i];
                count = 1;
            }
            else if (ar[i] == height){
                count++;
            }
        }
        return count;
    }
        • Sachith_M + 1 comment

          Yes for this one it looks easy to use initial ... I was wondering about using the bubble sort for all kinds these qs..
          Thank you for this code Its great

          • Alex_Marble + 1 comment

            Bubblesort i believe averages O(n^2), so i believe quicksort will generally be faster. For most of the questions on here its likely not worth using a sort as the benefits wouldn't be seen on only one use of the data. I think Linq is probably a better choice then a sort in this scenario but im not 100% sure.

            • Sachith_M + 0 comments

              yeah I agree with that.. Thanks bro.. :)

    • matthew_zilkie + 1 comment
      Did you try using c++ std::sort(ar.begin(), ar.end()); ? I did and it worked flawlessly.

int birthdayCakeCandles(int n, vector<int> ar) {
// Complete this function
sort(ar.begin(), ar.end());
int max = ar[ar.size() -1];
int count = 0;
for(auto num : ar) {
    if(num == max) ++count;
}
return count;

      }

      • vominhhuy008 + 1 comment

        Can you explain it please ? thanks

        • pbpraveen1988 + 0 comments

          They are just asking the count of candles blow off by birthday guy.

          Only heighted candles can be blow off , so we just need to find the count of heighted candles from array.

          a) Sort the array in ascending order , so you will have the sorted array with high values as last

          b) Get the last value in array and find out the count with that value. Thats it.

    • deepuvattikonda + 0 comments

      Thanks a lot!!.I was just wondering where did i go wrong..Thanks a lot again