- Practice
- Algorithms
- Greedy
- Priyanka and Toys
- Discussions

# Priyanka and Toys

# Priyanka and Toys

roadatlas + 4 comments Going to be honest here and say that this is my third foray into HackerRank (first one was a work thing, second one was a quiz for a potential job opportunity) and I have to say that these test write-ups for what is expected is REALLY difficult to suss out.

No, I'm not a college graduate, no I don't have extensive experience in high level math, but I'm pretty good at reading comprehension and the way this stuff is written makes my head hurt trying to figure out what is expected.

And I've been doing code reading and writing for a living for the past 25 years.

Perhaps you guys could offer a tutorial on how to read the test descriptions given that the use of this site for applicant filtering seems to have become an industry standard?

Just a thought.

Thanks! Mike Poz

juharri3 + 0 comments Unless this problem was rewritten since your comment I have to say this is not even close to one of the hardest ones to understand on this site. But I know exactly what you mean in general. Basically if the description is too heavy with complex math jargon just try skipping to the examples or reading the discussion section.

tzych + 0 comments Well, yes, they can be hard to comprehend sometimes. Consider it practice for the kinds of requirements documents youâ€™ll get :)

sarathy_v_krish1 + 2 comments C++ solution :

int toys(vector<int> w) { sort(w.begin(), w.end()); int i=0, count=0, base; while(i!=w.size()) { count++; base = w[i]; while(i!=w.size() && w[i]<=base+4) i++; if (i==w.size()) break; } return count; }

dilipp02 + 0 comments Slightly better if I am not mistaken:

int toys(vector<int> w) { int cnt=0, x=-1; sort(w.begin(), w.end()); for(int i=0 ; i<w.size() ; i++) if(w[i]>x){ x=w[i]+4; cnt++; } return cnt; }

qaseem_hasan_ + 0 comments I am not sure if that break condition is necessary or not, I had pretty much the same answer as yours without the break, since the while loop has the break condition and it passed all the tests.

Can you explain the purpose of that break condition?

excerption + 0 comments I think this one was very easy.

humoyun_ahmad + 4 comments I think the question is a bit ambigious: "Minimum units with which Priyanka could buy all of toys", I think "Minimum group of units with which Priyanka could buy all of toys" would explain the problem statement better, and in the given example it would be [(1,2,3),(10),(17)] -> 3 groups of units

Ashwin_522 + 0 comments how can you think in that way here the remaining two aRE LEFT so you considered each as a unit it isnt same right for all testcases

moraish_kapoor + 0 comments thank heavens for this comment.

juanl9sd + 0 comments 1 Unit is the cost of each toy

robencom + 0 comments Thanks for the clarification.

gauravdhingra_g1 + 4 comments I am sharing my solution below, feel free to leave comments please.

#!/usr/bin/python3 N = int(input()) W = set(map(int, input().split())) i = 0 while len(W) > 0: i += 1 m = min(W) W = W.difference(set(range(m, m + 5))) print(i)

AffineStructure + 0 comments wow, this is really good.

tonghuixiang01 + 0 comments import sys def toys(w): w = set(w) a = 0 while len(w) >0: z = min(w) a += 1 w = list(filter(lambda x: x > z + 4, w)) return a # Complete this function if __name__ == "__main__": n = int(input().strip()) w = list(map(int, input().strip().split(' '))) result = toys(w) print(result)

another way

NotAliceOrBob + 0 comments I like this too, but time complexity of set operations might be something to consider.

https://wiki.python.org/moin/TimeComplexity

Appears that set difference in Python is O(n).

tzych + 0 comments Pretty much what I did, but I think my syntax is worth a look; it seems more Pythonic to me.

`def toys(w): ws = set(w) ct = 0 while ws: mw = min(ws) ws -= set(range(mw, mw+5)) ct += 1 return ct input() w = [int(s) for s in input().split()] print(toys(w))`

saif01md + 3 comments import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { public static void main(String[] args) { /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */ Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int[] a=new int[n]; for(int i=0;i<n;i++){ a[i]=sc.nextInt(); } Arrays.sort(a); int cost=1; int p=a[0]; for(int i=0;i<n;i++){ if(a[i]>p+4){ cost=cost+1; p=a[i]; } } System.out.println(cost); } }

bobby_teja + 0 comments Simple and Elegant!!

mmitalee + 0 comments amazing!

craig31 + 0 comments Inefficient, since you're adding 4 every loop iteration when you only need to add it when the p value changes.

sonupanchal + 9 comments this passes all test cases.

int cmpfunc (const void * a, const void * b)

{ return (

*(int*)a -*(int*)b ); }int main() {

`int n,i,x,y,c=1; int a[100000]={0}; scanf("%d",&n); for(i=0;i<n;i++) scanf("%d",&a[i]); qsort(a, n, sizeof(a[0]), cmpfunc); x=a[0]; y=x+4; for(i=0;i<n;i++) { if(a[i]>=x && a[i]<=y) continue ; else { c++; x=a[i]; y=x+4; } } printf("%d",c); return 0;`

}

driftwood + 2 comments This can be accomplished more efficiently, with respect to both time and space complexity!

ayanparbat + 2 comments only fst &lst case passes

warrior_of_light + 1 comment Mine too. did you found the problem??

ertiwary + 0 comments equal too missing probably u uses

kakadiyaraj1999 + 0 comments bcz you forget to sort array .

diogosnows + 0 comments I used a bitvector and solved in O(N). I'd be interested to know how you optimised for space :)

EDIT: Here's my solution (not including loading the weights), ONLY OPEN AFTER SOLVING! http://pastebin.com/J7f9G3EV

msharp_oh + 0 comments This is exactly the same algorithm I worked out in Python. Simple, yet effective.

preetishkakkar + 0 comments This is not correct solution, Please check your code

shantanusalil + 0 comments nice algo

sam1064max + 1 comment This can be done in O(n). Check out counting sort.

kapploneon + 0 comments It will require Space complexity of O*(w). So it is basically trading of space vs time complexity.

kashish007 + 0 comments my program is not working with this solution so can u help pleasee !!!!!

dsncode + 0 comments [deleted]dsncode + 0 comments it works! thanks for your insight :) below a scala implementation. just input toys weight array and done.

def totalCost(toys_list:List[Int]):Int={ def toBuyToys(arr:List[Int],ref:Int,acc:Int):Int= arr match{ case Nil => acc case x :: xs =>{ if(x>=ref && x<=(ref+4)) toBuyToys(xs,ref,acc) else toBuyToys(xs,x,acc+1) } } val toys_sorted = toys_list.sorted toBuyToys(toys_sorted,toys_sorted.head,1) } println(totalCost(toy_list))

sameerjadhavweb + 0 comments **Java 8**static int toys(int[] w) { Arrays.sort(w); int count = 1; int curr = w[0] + 4; for (int i = 1; i < w.length; i++) { if (w[i] > curr) { count++; curr = w[i] + 4; } } return count; }

Sort 229 Discussions, By:

Please Login in order to post a comment