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.
int main() {
int n,ar_i;
scanf("%i", &n);
int *ar = malloc(sizeof(int) * n);
for(ar_i = 0; ar_i < n; ar_i++){
scanf("%i",&ar[ar_i]);
}
int result = birthdayCakeCandles(n, n, ar);
printf("%d\n", result);
return 0;
}
BRO THIS CODE SAYS TIME LIMIT EXCEEDED PLEASE HELP
intbirthdayCakeCandles(intn,vector<int>ar){// Complete this functionintmax=ar[0];intcount=0;for(inti=0;i<n;i++)if(ar[i]>max)max=ar[i];for(inti=0;i<n;i++)if(ar[i]==max)count++;returncount;}
just an optimization, even though in this case your code is fine:
if you try an array with negatives, then you ll never get inside your if-statements. so the numMaxHeight will never change, so you dont really compute it in such cases.
so this solution for an array with negatives, where the max negative appears more than once, will fail. eg [-1, -1]
proposed solution: set numMaxHeight = 0 on initialization
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
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;
while(std::cin>>n){// for each candle n check:if(max<n){// does n set a new record in height?max=n;// if that's so, then n is the new max heightc=1;// and the counter c must be set to 1 again. "!!" is a cheap trick to convert any value different from 0 into 1}else{// otherwise check if the new candle is as tall as maxif(max==n)c++;// in that case, add 1 to counter (otherwise add 0)}}
Nice one. I arrived at same algo in C, minus the one liner ternary. Looks neat, I like it. Although I'd be curious if there is not a small performance loss of doing:
c=!!(expr);
vs
(expr);c=1;
the former may require additional conditional logic depending on architecture (for instance x86 - http://riffwiki.com/MOV_(x86_instruction) - the MOV instruction doesn't affect ZeroFlag, so I'd guess CPU would have to evaluate whether your expr results in a non-zero value. It's obvious to us as we can see the wider context of the algorithm, but not the CPU)
It is not CPU that analyses your c++, the compiler does. CPU doesn't "thin" but compiler does. It is really pointless to "optimize" your code this way because compiler is required to emit assembly that does what is ment but in which order and through which instructions, it is not specified. You better belive it does good job. You express c++ although it is slower than ++c: there is no way the compiler would use slower version if it doesn't afect the program flow. With no optimization flags may be.
cin.ignore() ignores the input of number of candles as its not needed in his algorithm and the input in loop works as long as the input isnt 0 or null, while loop works for any number in the test condition.
if you have case like 20,40,90,90,90 so you see according to your code in max variable value will 20 and frequency will be 1 and after the loop ends your result will be 4 instead it should be 3
because you have allocated memory to pointer ar using malloc function before taking the value of n from user. you should first take input n from user and then allocate memory to the pointer, i.e.
first use scanf("%d",&n);
then write int ar=(int)malloc(sizeof(int)*n);
Birthday Cake Candles
You are viewing a single comment's thread. Return to all comments →
A compact C++ solution:
Like this a lot. Thanks.
`c
include
include
include
include
include
include
include
int birthdayCakeCandles(int n, int ar_size, int* ar) { // Complete this function int i,j,temp,count=0,b; for(i=0;i
return count; }
int main() { int n,ar_i; scanf("%i", &n); int *ar = malloc(sizeof(int) * n); for(ar_i = 0; ar_i < n; ar_i++){ scanf("%i",&ar[ar_i]); } int result = birthdayCakeCandles(n, n, ar); printf("%d\n", result); return 0; } BRO THIS CODE SAYS TIME LIMIT EXCEEDED PLEASE HELP
use c++ and you'll be fine
this code was working on some test case but not all please help me
/*You should do like this... */
In java, maybe this way can help you! :)
just an optimization, even though in this case your code is fine: if you try an array with negatives, then you ll never get inside your if-statements. so the numMaxHeight will never change, so you dont really compute it in such cases. so this solution for an array with negatives, where the max negative appears more than once, will fail. eg [-1, -1]
proposed solution: set numMaxHeight = 0 on initialization
You can simplify it like this:
int max=ar[0]; int count=0; for(int i=0;imax){ max=ar[i]; count = 1; //Reinitialize count if you found a new max }
} return count;
I this case you are traversing the vector only once.
i did the same thing.But it is showing me 4 test cases failed.
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:
I tried this
It is failing the test case
100000 followed by 100000 times 9999999 (as height of candles(array values)).
Pass all Testcases..
Try This
static int birthdayCakeCandles(int[] ar) {
need to add one more check in while condition for all the array elements with same value
while ( i > -1 && a[i--] == tallest ) { count++; }
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
}
ar[i]-max==0 in second if worked for me
sandeep did u use unsigned long or any other data type which allows you to take in large amounts of data?
Since height of the candle is always at least 1, you can safely assume max = 0; Then loop all at once, you dont need a double loop. (Java syntax)
You don't need the second loop. Checking of equal can be done in the else of
if(ar[i] > max)thank you!
Ask yourself a few questions:
-The number of highest candles
-I need to know what the highest candle is.
-I need to know how many of them there are.
-Simple comparison should work for knowing what the highest is. Just store it in a var and reset when I find one that's bigger.
-Store the quantity in a var, increment it whenever I find one of the Highest candles and reset it each time I find a new highest candle.
i'm not into c++, but this looks savage :)
Can you explain more about the complicated, savage version of that ternery statement? I really want to know this nifty code!
can be translated as:
Too good
Nice one !!
How the hell "!!" trick work? I have no idea...
When you negate '!' a value diferent than 0 you will get 0, then if you negate 0 you will get 1 so..
!anyNonZeroVal == 0 !0 == 1
!!anyNonZeroVal == 1;
Good!
nice one
nice. thank you
Well I came up with similar algorithm, so thumbs up. Also seems like solution in editorial goes though array twice, and this goes only once.
hats off..
Nice one. I arrived at same algo in C, minus the one liner ternary. Looks neat, I like it. Although I'd be curious if there is not a small performance loss of doing:
vs
the former may require additional conditional logic depending on architecture (for instance x86 - http://riffwiki.com/MOV_(x86_instruction) - the MOV instruction doesn't affect ZeroFlag, so I'd guess CPU would have to evaluate whether your expr results in a non-zero value. It's obvious to us as we can see the wider context of the algorithm, but not the CPU)
thanks
It is not CPU that analyses your c++, the compiler does. CPU doesn't "thin" but compiler does. It is really pointless to "optimize" your code this way because compiler is required to emit assembly that does what is ment but in which order and through which instructions, it is not specified. You better belive it does good job. You express c++ although it is slower than ++c: there is no way the compiler would use slower version if it doesn't afect the program flow. With no optimization flags may be.
This is brilliant!
nice why didn't i think of this sooner
TYSM!! Helped me a lot..
I did the same thing but my code fails for some tests :O
I tried same in java. It worked! Thanks (:
Very nice -- thanks for nudging me to think about it as a streaming algorithm :-)
It's cool! Thanks!
I dont understand how cin.ignore(); works... And how you can feed input into loop condition...
cin.ignore() ignores the input of number of candles as its not needed in his algorithm and the input in loop works as long as the input isnt 0 or null, while loop works for any number in the test condition.
can u give the solution for c programming.
int main(){ int n; scanf("%d",&n); int *height = malloc(sizeof(int) * n); int max=height[0]; int count=0; for(int height_i = 0; height_i < n; height_i++){ scanf("%d",&height[height_i]); } for(int i=1; imax){ max=height[i]; } } for(int k=0; k
can u please tell me why this code is not able to pass all the test case
// the code goes here..
int main(){ int n,i,max=0,frequency=0;
int ar =(int) malloc(sizeof(int) * n);
}
include
include
include
include
include
include
include
int birthdayCakeCandles(int n,int a[]) { long long int i,max=0,d=0; for(i=0;imax) { d=1; max=a[i]; } else if(a[i]==max) { d++; } } return d;
}
int main() { int n; scanf("%i", &n); int *ar = malloc(sizeof(int) * n); for(int ar_i = 0; ar_i < n; ar_i++){ scanf("%i",&ar[ar_i]); } int result = birthdayCakeCandles(n,ar); printf("%d\n", result); return 0; }
Return frequency to calling function instead of printig here.
if you have case like 20,40,90,90,90 so you see according to your code in max variable value will 20 and frequency will be 1 and after the loop ends your result will be 4 instead it should be 3
your else if part should be in for loop and in if statement remove that frequency set otherwise max number counted twice.
your are returning count of candles of same height. We have to return the number of candle he/she can blow out.
you havent calculated the final max value and processed it before hand for comparision
what is max before entering the for loop??
because you have allocated memory to pointer ar using malloc function before taking the value of n from user. you should first take input n from user and then allocate memory to the pointer, i.e. first use scanf("%d",&n); then write int ar=(int)malloc(sizeof(int)*n);
hope, you understand.
compact indeed, great job!
Yeah, yours is way cleaner than mine
Why we need vector here?
good solution
Solid solution. Wouldn't it be more efficient to do a for loop such as
So you can avoid calling both sort and reverse? Not trying to correct you, genuine question
it will not pass all the testcases
Great one
awesome
What is the use of cin.ignore() please tell me
That's so nice.Thanks
what is the role of cin.ignore() ?? what if we do not write that line?
wao! stupendous code!
Can someone explain to me :
max < n ? c = !!(max = n) : c += max == n;
bro use python3 :
No looping, no veriables, no mess
wow this is crazy, thank you
i did the same. python is so useful when it comes to counting the number of occurences
Cute