HackerRank Candies Problem Solution

In this post, we will solve HackerRank Candies Problem Solution. Alice is a kindergarten teacher. She wants to give some candies to the children in her class.  All the children sit in a line and each of them has a rating score according to his or her performance in the class.  Alice wants to give at least 1 candy to each child. If two children sit next to each other, then the one with the higher rating must get more candies. Alice wants to minimize the total number of candies she must buy.

Example
arr = [4, 6, 4, 5, 6, 2]
She gives the students candy in the following minimal amounts: [1, 2, 1, 2, 3, 1]. She must buy a minimum of 10 candles.

Function Description

Complete the candies function in the editor below.

candies has the following parameter(s):

  • int n: the number of children in the class
  • int arr[n]: the ratings of each student

Returns

  • int: the minimum number of candies Alice must buy

Input Format
The first line contains an integer, n. the size of arr.
Each of the next in lines contains an integer arr[i] indicating the rating of the student at position i

Sample Input 0

3
1
2
2

Sample Output 0

4

Explanation 0

Here 1, 2, 2 is the rating. Note that when two children have equal rating, they are allowed to have different number of candies. Hence optimal distribution will be 1, 2, 1.

Sample Input 1

10
2
4
2
6
1
7
8
9
2
1

Explanation 1

Optimal distribution will be 1, 2, 1, 2, 1, 2, 3, 4, 2, 1.

Sample Input 2

8
2
4
3
5
2
6
4
5

Sample Output 2

12

Explanation 2

Optimal distribution will be 12121212

HackerRank Candies Problem Solution
HackerRank Candies Problem Solution

Candies C Solution

//
//  main.c
//  Candles
//
//  Created by Roberto Caporicci on 21/07/12.
//  Copyright (c) 2012 __MyCompanyName__. All rights reserved.
//

#include <stdio.h>
#include <stdlib.h>


int parse_n();
void parse_input(int n,int *scores,int* candles);
int count_candles(int* candles, int n);
void compute_candles(int* scores, int* candles, int n);
void adjust_back(int* candles, int* scores, int start_pos);
void print_array(int* array, int n);

int main(int argc, const char * argv[])
{

    int n;
    int tot_candles;
    int* scores=NULL;
    int* candles=NULL;
    n=parse_n();
    scores=(int *)malloc(n*sizeof(int));
    candles=(int *)malloc(n*sizeof(int));
    parse_input(n,scores,candles);
    compute_candles(scores,candles,n);
    tot_candles=count_candles(candles,n);
    //printf("scores:\n");
    //print_array(scores, n);
    //printf("candles:\n");
    //print_array(candles, n);
    printf("%d",tot_candles);
    return 0;
}

int parse_n(){
    int temp;
    scanf("%d",&temp);
    return temp;
}

void parse_input(int n,int *scores,int* candles){
    
    int i;
    for (i=0;i<n;i++){
        scanf("%d",&scores[i]);
        candles[i]=1;
    }
}

int count_candles(int* candles, int n){

    int i=0;
    for (int j=0;j<n;j++){
        i+=candles[j];
    }
    return i;
}

void compute_candles(int* scores, int* candles, int n){
    
    int i; // progress
    for (i=0;i<(n-1);i++){
        if (scores[i]>scores[i+1] && candles[i]<=candles[i+1]){
                candles[i]++;
                adjust_back(candles,scores,i);   
            
        }
        else if (scores[i]<scores[i+1])
            candles[i+1]=candles[i]+1;
    }

    
}

void adjust_back(int* candles, int* scores, int start_pos){
    
    if (start_pos==0)
        return;
    if (scores[start_pos]>=scores[start_pos-1])
        return;
    if (candles[start_pos-1]>candles[start_pos])
        return;
    else {
        candles[start_pos-1]++;
        adjust_back(candles, scores, start_pos-1);
    }

}

void print_array (int* array, int n){
    int i;
    for (i=0;i<n;i++){
        printf("[%d] = %d\n",i,array[i]);
    }
}

Candies C++ Solution

#include<bits/stdc++.h>

using namespace std;

struct data
{
    long long pos,val;
};

bool cmp(data A,data B)
{
    if(A.val<B.val)return 1;
    else return 0;
}
data info[100005];
long long got[100005],n,rat[100005];
int main()
{
    register int i,j;
    long long counter=0;
    cin >> n;

    for(i=1;i<=n;i++)
    {
        cin >> rat[i];
        info[i].pos=i;
        info[i].val=rat[i];
    }
    rat[0]=10000000;
    rat[n+1]=10000000;
    sort(info+1,info+n+1,cmp);

    for(i=1;i<=n;i++)
    {
        int pos = info[i].pos;

        long long g1=0,g2=0;
        if(rat[pos]>rat[pos-1])g1 = got[pos-1]+1;
        if(rat[pos]>rat[pos+1])g2 = got[pos+1]+1;

        got[pos]=max(g1,g2);
    }

    for(i=1;i<=n;i++)
    {
        counter+= got[i]+1;
    }
    cout << counter;
}

Candies C Sharp Solution

using System;
using System.Collections.Generic;

namespace Solution
{
    class Solution
    {
        public static void Main(string[] args)
        {
            var line1 = System.Console.ReadLine().Trim();
            var N = Int32.Parse(line1);

            var input = new List<Int32>();

            for (var i = 0; i < N; i++)
            {
                input.Add(Int32.Parse(System.Console.ReadLine().Trim()));
            }

            var result = SolveCandies(input);

            System.Console.WriteLine(result.ToString().Trim());
        }



        public static int SolveCandies(List<Int32> studentRankings)
        {

            var requiredCandies = 0;

            // Split into sub arrays.

            var previousValue = 0;
            var subArray = new List<Int32>();
            var incline = true;
            var midIndex = 0;
            var startCandiesAt = 1;

            foreach (var student in studentRankings)
            {
                if (incline)
                {
                    if (previousValue <= student)
                    {
                        subArray.Add(student);
                        previousValue = student;
                        midIndex = subArray.Count - 1;
                    }
                    else
                    {
                        subArray.Add(student);
                        previousValue = student;
                        incline = false;
                    }
                }
                else
                {
                    if (student <= previousValue)
                    {
                        subArray.Add(student);
                        previousValue = student;
                    }
                    else
                    {
                        requiredCandies += SolveSubArray(subArray, midIndex, startCandiesAt);
                        startCandiesAt = 2;

                        incline = true;
                        midIndex = 0;
                        subArray = new List<Int32>();
                        subArray.Add(student);
                        previousValue = student;
                    }
                }
            }

            requiredCandies += SolveSubArray(subArray, midIndex, startCandiesAt);

            return requiredCandies;
        }


        public static int SolveSubArray(List<Int32> studentRankings, int middle, int startCandiesAt)
        {
            var totalCandies = 0;
            var candyToStudent = startCandiesAt;

            var lastValue = 0;
            var middleAssignedValue = 0;

            // Go up
            for (int i = 0; i <= middle; i++)
            {
                if (studentRankings[i] == lastValue)
                {
                    candyToStudent = 1;
                }

                if (i == middle)
                {
                    middleAssignedValue = candyToStudent;
                }

                lastValue = studentRankings[i];
                totalCandies += candyToStudent;
                candyToStudent++;
            }


            lastValue = 0;
            candyToStudent = 1;

            // Go down
            for (int i = studentRankings.Count - 1; i > middle; i--)
            {
                if (studentRankings[i] == lastValue)
                {
                    candyToStudent = 1;
                }

                lastValue = studentRankings[i];
                totalCandies += candyToStudent;
                candyToStudent++;
            }

            // Check Middle
            if (candyToStudent >= middleAssignedValue)
            {
                totalCandies -= middleAssignedValue;
                totalCandies += candyToStudent;
            }

            return totalCandies;

        }
    }
}

Candies Java Solution

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {

    /*
     * Complete the 'candies' function below.
     *
     * The function is expected to return a LONG_INTEGER.
     * The function accepts following parameters:
     *  1. INTEGER n
     *  2. INTEGER_ARRAY arr
     */

    public static long candies(int n, List<Integer> arr) {
    // Write your code here
        long[] lr = new long[n];
        long[] rl = new long[n];
        
        lr[0] = 1;
        for (int i = 1; i < lr.length; i++) {
            if (arr.get(i) > arr.get(i - 1)) {
                lr[i] = lr[i - 1] + 1;
            } else {
                lr[i] = 1;
            }
        }
        
        rl[rl.length - 1] = 1;
        for (int i = rl.length - 1 - 1; i >= 0; i--) {
            if (arr.get(i) > arr.get(i + 1)) {
                rl[i] = rl[i + 1] + 1;
            } else {
                rl[i] = 1;
            }
        }
        
        long c = 0;
        for (int i = 0; i < n; i++) {
            c += Math.max(lr[i], rl[i]);
        }
        
        return c;
    }

}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int n = Integer.parseInt(bufferedReader.readLine().trim());

        List<Integer> arr = IntStream.range(0, n).mapToObj(i -> {
            try {
                return bufferedReader.readLine().replaceAll("\\s+$", "");
            } catch (IOException ex) {
                throw new RuntimeException(ex);
            }
        })
            .map(String::trim)
            .map(Integer::parseInt)
            .collect(toList());

        long result = Result.candies(n, arr);

        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();

        bufferedReader.close();
        bufferedWriter.close();
    }
}

Candies JavaScript Solution

function processData(input) {
    var lines = input.split('\n').map(Number);
    var children = lines.slice(1);
    var mins = [];
    mins.push(1);
    //console.log('first');
    for (var i = 1; i < children.length; i++) {
        minToAdd = 1;
        if (children[i] > children[i - 1]) {
            minToAdd = mins[i - 1] + 1;
        }
        mins.push(minToAdd);
        //console.log(i + ' ' + mins);
    }
    
    //console.log('second');
    for (var j = children.length - 1; j > 0; j--) {
        if (children[j - 1] > children[j] && mins[j] >= mins[j - 1]) {
            mins[j - 1] = mins[j] + 1;
        }
        //console.log(j + ' ' + mins);
    }
    
    
    var total = 0;
    for (var i = 0; i < mins.length; i++) {
        total += mins[i];
    }
    console.log(total);
    //Enter your code here
} 

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});

Candies Python Solution

from collections import deque
    
N = int(input())
ratings = []
for i in range(N) :
    ratings.append(int(input()))

f = deque([1])
r = deque([1])
for i in range(1,N) :    
    if ratings[i] > ratings[i-1] :
        f.append(f[-1] + 1)
    else :
        f.append(1)
        

for i in reversed(range(N-1)) :
    if ratings[i] > ratings[i+1] :
        r.appendleft(r[0] + 1)
    else :
        r.appendleft(1)
        
output = 0

for i in range(N) :    
    output += max(f[i],r[i])
    
print(output)