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. Candies
  5. Discussions

Candies

Sort by

recency

|

674 Discussions

|

  • chmielewski_wik1
     + 0 comments

    My solution is based on observation that each student should get at least d candies, where d is the length of the longest decreasing subsequence in arr starting from this student. E.g. if scores are 8 6 3, then first student should get at least 3 candies, second should get at least 2, etc.

    On the other hand, each student should get at least one more candy then their left colleague if they have a higher score. That is why we have the formula:

    candies[i] = max(longest_decreasing_subsequence[i], candies[i - 1] + 1)

    public  static  long candies(int n, List<Integer> arr) {

int[] decreasing = new  int[n];
decreasing[n - 1] = 1;
for (int i = n - 2; i >= 0; --i) {
	decreasing[i] = arr.get(i) > arr.get(i + 1)
	? decreasing[i + 1] + 1
	: 1;
}

long candiesGiven = decreasing[0];
for (int i = 1, candiesLast = decreasing[0]; i < n; ++i) {
	candiesLast = arr.get(i) > arr.get(i - 1)
	? Math.max(candiesLast + 1, decreasing[i])
	: decreasing[i];

	candiesGiven += candiesLast;
}

return candiesGiven;
}

  • rajivaiyer
     + 0 comments

    My Java 8 solution, passing all test cases, for a Max Score of 50:

    The code is fairly simple & self-explanatory.

    public static long candies(int n, List<Integer> arr) {
        // Write your code here
        
        // dpL[i] = Min number of candies needed for child 'i' 
        //          when only considering the left neighbor constraint.

        // dpR[i] = Min number of candies needed for child 'i' 
        //          when only considering the right neighbor constraint.

        int[] dpL = new int[n];
        int[] dpR = new int[n];

        // Every child gets at least one candy.
        // Set dpL[i] = 1 and dpR[i] = 1 for all 'i'.
        Arrays.fill(dpL, 1);
        Arrays.fill(dpR, 1);

        // DP from Left to Right + DP from Right to Left in a Single Combined Loop
        for (int i = 1 , j = (n - 2) ; (i < n) || (j >= 0) ; i++, j--) {

            // DP from Left to Right
            if (i < n && arr.get(i) > arr.get(i - 1)) {
                dpL[i] = dpL[i - 1] + 1;
            }

            // DP from Right to Left
            if (j >= 0 && arr.get(j) > arr.get(j + 1)) {
                dpR[j] = dpR[j + 1] + 1;
            }

        }

        // Combine 'dpL' & 'dpR' results
        long minTotalCandies = 0;
        for (int i = 0; i < n; i++) {
            minTotalCandies += Math.max(dpL[i], dpR[i]);
        }

        return minTotalCandies;
    }

  • vs883140
     + 0 comments

    public static long candies(int n, List arr) { // Write your code here

        long[] candies = new long[n];
    Arrays.fill(candies, 1);

    for (int i=1; i<n; i++) {
        if (arr.get(i)>arr.get(i-1)) {
            candies[i] = candies[i-1]+1;
        }
    }

    for (int i=n-2; i>=0; i--) {
        if (arr.get(i)>arr.get(i+1)) {
            candies[i] = Math.max(candies[i], candies[i+1]+1);
        }
    }
    long sum = 0;
    for (long c : candies) {
        sum += c;
    }
    return sum;
}``

  • write2piyushkum1
     + 0 comments

    Java:

        public static long candies(int n, List<Integer> arr) {
        long[] candies = new long[n];
        Arrays.fill(candies, 1);
        // Left to right
        for (int i=1; i<n; i++) {
            if (arr.get(i)>arr.get(i-1)) {
                candies[i] = candies[i-1]+1;
            }
        }
        // Right to left
        for (int i=n-2; i>=0; i--) {
            if (arr.get(i)>arr.get(i+1)) {
                candies[i] = Math.max(candies[i], candies[i+1]+1);
            }
        }
        return Arrays.stream(candies).sum();
    }

  • lukegemmell16
     + 0 comments

    C++ Solution

    long long candies(unsigned n, vector<unsigned> arr) {
    vector<unsigned> candies(arr.size(), 1);
    
    for(unsigned i = 1; i < n; i++)
        if(arr[i] > arr[i-1])
            candies[i] = candies[i-1] + 1;
    
    for(int i = n - 2; i >= 0 ; i--)
        if(arr[i] > arr[i + 1])
            candies[i] = max(candies[i + 1] + 1, candies[i]);

    return accumulate(candies.begin(), candies.end(), static_cast<long long>(0));   
}