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. Prepare
  2. Algorithms
  3. Greedy
  4. Priyanka and Toys
  5. Discussions

Priyanka and Toys

Sort by

recency

|

500 Discussions

|

  • safee7
     + 1 comment

    C++ implementation : Intution:- First sort the array and then check with the first element(threshold) if the element is <= threshold+4 , keep going and when it fails the condition increment the answer.

    int toys(vector<int> w) {
    sort(w.begin(),w.end());
    int ans=1;
    int n=w.size();
    int j=0;

        int threshold = w[0]+4;
        
        while(j < n){
            if(w[j] <= threshold){
                j++;
            }
            else {
                ans++;
                threshold = w[j]+4;
                j++;
                } 
            }
        
    return ans;
}

  • alban_tyrex
     + 0 comments

    Here is my c++ solution, you can watch the explanation here : https://youtu.be/Es5l0jbSH9I

    int toys(vector<int> w) {
    sort(w.begin(), w.end());
    int result = 1, mi = w[0];
    for(int item: w){
        if(item > mi + 4){
            mi = item;
            result++;
        }
    }
    return result;
}

  • emhhacker
     + 0 comments

    My Java solution with o(n log n) time complexity and o(1) space complexity:

    public static int toys(List<Integer> w) {
        // goal: determine the min amt of subarrays that can be created based on the container rule
        if(w.size() == 1) return 1;
        
        //sort arr
        Collections.sort(w);
        
        //iterate over each val until it reaches the max container val and increment the container count
        int maxContainerVal = w.get(0) + 4;
        int containers = 1;
        for(int i = 0; i < w.size(); i++){
            if(w.get(i) > maxContainerVal){
                maxContainerVal = w.get(i) + 4;
                containers++;
            }
        }
        return containers;
    }

  • patrickgao2020
     + 0 comments

    Here is my Python solution!

    def toys(w):
    minimum = min(w) + 4
    containers = 1
    w = sorted(w)
    for toy in w:
        if toy > minimum:
            minimum = toy + 4
            containers += 1
    return containers

  • CS_2201640100111
     + 0 comments
    int toys(vector<int> w) {
    sort(w.begin(),w.end());
    int c=0;
    size_t i = 0;
    while (i < w.size()) {
        int max = w[i] + 4;
        while (i < w.size() && w[i] <= max) {
            i++;
        }
        c++;
    }
    
    return c;
}