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.
TypeScript solution. Despite some optimizations, it still fails some tests due to time constraints. A JS priority queue / heap queue would be nice...
// Finding the items in the array and removing them is// faster than sorting and popping.// I am sure this function could be written in a more compact fashion,// but it works for now.// This function assumes, the array has at least 2 elementsfunctionfindLeastTwoAndRemove(arr:number[]):[number,number]{letleast=Number.MAX_VALUE;letleastI=-1;letleast2nd=Number.MAX_VALUE;letleast2ndI=-1;// find the 2 smalles values and their indicesfor(leti=0;i<arr.length;++i){constcurr=arr[i];if(curr<least){least2nd=least;least2ndI=leastI;least=curr;leastI=i;}elseif(curr<least2nd){least2nd=curr;least2ndI=i;}}// remove the values from the array.// splice from behind, so that we don't shift the arrayif(leastI>least2ndI){arr.splice(leastI,1);arr.splice(least2ndI,1);}else{arr.splice(least2ndI,1);arr.splice(leastI,1);}return[least,least2nd];}functioncookies(k:number,arr:number[]):number{// we don't care about the cookies that are already sweet enoughconstlessK=arr.filter(value=>value<k);// no savory cookies left? we'll we're done here!if(lessK.length===0)return0;// did we already find cookies that were sweet enough? It's important// to remember, because we threw them away earlierletfoundSweeter=arr.length>lessK.length;letoperations=0;// I'm not the biggest fan of this while(true) loop here,// but it does its job!while(true){if(lessK.length===0)returnfoundSweeter?operations:-1;// if there is only one item left, it must be smaller than K.// So if we found a sweeter one, we still need an extra operation// otherwise it's game overif(lessK.length===1)returnfoundSweeter?operations+1:-1;// perform the operationconst[least,least2nd]=findLeastTwoAndRemove(lessK);constnewCookie=least+2*least2nd;operations+=1;// we only need to add the cookie, if its sweetness is smaller than k// otherwise it is enough to know, that we had one that was sweet enough.// This way, we keep our array small.if(newCookie<k){lessK.push(newCookie);}else{foundSweeter=true;}}}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Jesse and Cookies
You are viewing a single comment's thread. Return to all comments →
TypeScript solution. Despite some optimizations, it still fails some tests due to time constraints. A JS priority queue / heap queue would be nice...