- 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 + 1 comment 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; }

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))`

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; }

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.

__spartax + 6 comments my code friends

#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; vector<int> v(n); for(int i = 0; i < n; ++i) cin >> v[i]; sort(v.begin(), v.end()); int cost = 0; for(int i = 0; i < n; i = upper_bound(v.begin(), v.end(), v[i]+4) - v.begin()) cost++; cout << cost; return 0; }

I_am_Nobody + 1 comment can u explain i = upper_bound(v.begin(), v.end(), v[i]+4) - v.begin() statement? i mean how is an pointer being assigned to i???

__spartax + 1 comment `upper_bound`

returns a iterator to the element which is greater than`v[i]+4`

. while`v.begin()`

returns a iterator to the start of v. when the iterator returned by`upper_bound`

is subtracted from`v.begin()`

, i get the*offset*of the elementI_am_Nobody + 1 comment thanks :D

apurvparekh + 0 comments Good logic

rakeshKM + 0 comments nice code

AkashSarda + 0 comments Pardon me for I don't now c++. But basically, you are sorting and selecting the minimum, taking till minimum + 4 and resetting index to minimum + 4. Am I right?

iainws + 0 comments great use of upper_bound! thanks.

you can write:

for(auto it = v.begin(); it != v.end(); it = upper_bound(v.begin(), v.end(), *it + 4))cnt++;

ayushr2 + 5 comments sorting it would make it O(n logn) right? here is a O(n) solution

public static void main(String[] args) { Scanner scan = new Scanner(System.in); int[] arr = new int[10001]; int n = scan.nextInt(); for(int i = 0; i < n; i++) { arr[scan.nextInt()]++; } int ans = 0; for(int i = 0; i < 10001; i++) { if(arr[i] > 0) { i += 4; ans++; } } System.out.println(ans); }

however it takes space of array of length 10001.

lonewolff + 1 comment its not O(n) yours is constant of O(10e5+1) and to my surprise it worked, primarly because i think the test cases don't have duplicate values.

leoiii199241 + 0 comments even if there's duplicate, the check here if(arr[i] > 0) only count them once right? (where i is a specific weight)

gnakum7845 + 1 comment can you please explain me the logic....

ayushr2 + 2 comments hello! basically follow the above code which sorts the toys. here i am taking advantage of the fact that all values lie between 1 and 10^5. so make an array of that length and let index i represent the number of toys of weight i. this is called count sort which is O(n). then iterate from start and see if u hit a toy (count > 0). if so, increment counter by 4 since next 4 weights will be free.

gnakum7845 + 0 comments Thank you:)

anujaditya + 0 comments [deleted]

axel4u + 1 comment Nice solution. But you use counting sort, don't you? Also I think BitSet can save some space of array of length 10001.

`public static void main( String[] args ) { Scanner theScanner = new Scanner( System.in ); int n = theScanner.nextInt(); BitSet b = new BitSet( 10001 ); for( int i = 0 ; i < n ; i++ ) b.set( theScanner.nextInt() ); theScanner.close(); int count = 0; int next = b.nextSetBit( 0 ); while( next > -1 ) { count++; next = b.nextSetBit( next + 5 ); } System.out.print( count ); }`

anujaditya + 0 comments [deleted]

maurol + 0 comments Here's a solution in Python that is O(max(N, max(W))) in time, and is space efficient

`def toys(w): w = {weight: True for weight in w} containers = 0 max_w = max(w) i = 0 while i <= max_w: if w.get(i): containers += 1 i += 4 i += 1 return containers`

rahul0407 + 0 comments [deleted]

hari1999 + 1 comment #include<iostream> #include<algorithm> using namespace std; int main() { int n; cin>>n; int a[n]; for(int i=0;i<n;i++) cin>>a[i]; int b=0; int total=0; sort(a,a+n); b=a[0]; for(int i=1;i<n;i++) { if(a[i]-b>4) { total++; b=a[i]; } } cout<<total+1; }

This is a pretty short code passing all the test cases.

doradlanirosha9 + 0 comments yes this is nice a code

MukeshPanwar + 1 comment So I checked a unit case which I failed. Input : 0 2 9 10 13 16 17 17 18 19 Output : 3

This is not even possible taking into account all possibilities as below:

Take 0, Count=1,0+4=4 so FreeToys=(0,2), remaining ways=8...TotalWays=1+8=9 Take 2, Count=2,2+4=6 so FreeToys=(2), remaining ways=8...TotalWays=2+8=10 Take 9, Count=3,9+4=13 so FreeToys=(9,10,13), remaining ways=5...TotalWays=3+5=8 Take 10, Count=4,10+4=14 so FreeToys=(10,13), remaining ways=5...TotalWays=4+5=9 Take 13, Count=5,13+4=17 so FreeToys=(13,16,17,17), remaining ways=2...TotalWays=5+2=7 Take 16, Count=6,16+4=20 so FreeToys=(16,17,17,18,19), remaining ways=0...TotalWays=6+0=6 Take 17, Count=7,17+4=21 so FreeToys=(17,17,18,19), remaining ways=0...TotalWays=7+0=7 Take 17, Count=8,17+4=21 so FreeToys=(17,17,18,19), remaining ways=0...TotalWays=8+0=8 Take 18, Count=9,18+4=22 so FreeToys=(18,19), remaining ways=0...TotalWays=9+0=9 Take 19, Count=10,19+4=23 so FreeToys=(19), remaining ways=0...TotalWays=10+0=10

Final List of Possible ways = [9,10,8,9,7,6,7,8,9,10] Minimum way = 6

ZWarriors1 + 1 comment sorted: 0 2 9 10 13 16 17 17 18 19

on buying 0 got free 2 on buying 9 got free 10 13 on buying 16 got free 17 17 18 19

got 7 units for free hence ans:

3

dax_druminski + 0 comments [deleted]

kayathiri_gopi + 2 comments I could not understand the efficient approach explained in the editorial. Please help. Thanks.

shashank21jHackerRank Admin + 2 comments How are you trying to solve it?

kayathiri_gopi + 1 comment I have solved it by, Sorting the array, Finding toys whose weights are between min and min+4, Consider them as a unit, Loop till the end of sorted array

jjlearman + 1 comment Your solution is O(NlogN) due to having to sort the array. The editorial solution avoids sorting, at the cost of a constant-sized array (size related to one of the problem's constant parameters; call it M, so that solution is O(N)+O(M).

The editorial solution is pretty much the same as yours, except without having to sort the array; instead doing the first part (loop on N) that more or less has the same effect as sorting for the purposes of this problem. I don't want to go into too much detail here.

msram + 0 comments I have also done it with a usual O(N*log(N)) sorting mehtod. The solution in the editorial may be interpreted as a counting sort based algorithm, which is O(N). If the weights were arbitrary, then that may not have been possible. So conceptually both the solutions are the same.

Gryphon5 + 0 comments [deleted]

Martende + 1 comment I also did not understood the solution, its straitforward but how can i check and prove that this greedy solution is a real min.

bgreenfield + 0 comments if you get weight k you get all toys with weight k to k+4 free. if k is the lowest value in the array and you want to get all the toys you must buy it becuase there is no k less then the min you can buy and then get min weight free. once you buy the min then you never need to buy toys with wieght min to min+4 so you can remove these from the array. since we have to buy the lowest weight in the remainging array to have all the toys. its a recursive reductive proof.

vishva1994 + 1 comment Can there be a possibility of 2 toys having the same weight?

dheeraj + 0 comments Yes.

Sort 216 Discussions, By:

Please Login in order to post a comment