Styjun

I am trying to solve an hackerrank challenge in JavaScript, and although for most of the test instances my solution performs quite well, I keep getting a timeout for some of them (Hackerrank has it set for 10 seconds for JavaScript challenges). The problem is described below:

There are N children standing in a line. Initially the i-th child has a[i]
candies. Some of the children have more candies than others. You have
to make sure that every student has the same number of candies. In one
operation you can tell one of the children to give a single candy to
the left neighbour, or to the right one. How many operations do you
need to make sure every student has same number of candies? Print the
minimal possible number of operations. The input is a multiline
string, where the first line contains a single integer N, and the next
line contains N space separated integers.

I solved this problem by calculating which number of candies should be given to each and every kid, and then iterate the array containing the number of candies, either grabbing candies from the rightmost positions (in case the child wouldn't have enough), or passing candies to the right position (in case the child would have more than needed)

This is the code I used for the challenge:

function processData(input) /),
 n = tmp[0] 

 tmp.shift() // remove first element from tmp (the N variable)

 let s=0, a = tmp.map(function(ai) novo=parseInt(ai, 10);s+=novo;return(novo)),
 obj = s/n, ops = 0

 for(var i=0; i<n; i++) 

 if(a[i] > obj) 
 let moved = a[i]-obj
 a[i]-=moved
 a[i+1]+=moved
 ops+=moved
 
 else 
 for(var j=i+1; a[i] != obj; j++) 


 if(a[j]===0) 
 ops++
 
 else 
 let moved = Math.min(a[j], obj-a[i])
 a[i]+=moved
 a[j]-=moved
 ops+=moved
 
 
 

 //console.log(a)
 

 console.log(ops)

Any idea on what is the problem?

How would you optimise my code?

Link to the challenge : https://www.hackerrank.com/contests/coc1/challenges/candies-1

EDIT
After some optimisations, my solution now fails 3 of the test cases (the same ones it was failing before due to timeout). It was not a performance issue

The question is, how many moves do you need to have an avarage count for each children.

For example take this line of children,

1 4 2 7 1

where you start with the first children and look how much items it has and how many items it should have. Take the (absolute) difference for counting the moves and give the first child the average. The next children gets the delta of the first children. In this case after giving two items, it has then two items.

Then look at the next children in the line. Repeat the above and you get the count of moves for all children in a single loop.

 children moves 
--------------- -----
 1 4 2 7 1 2
<3 2> 2 7 1 1
 3 <3 1> 7 1 2
 3 3 <3 5> 1 2
 3 3 3 <3 3>
--------------- -----
 7

<x y> denotes a group of changing values

Example 2

 children moves 
--------------- -----
 7 4 2 1 1 4
<3 8> 2 1 1 5
 3 <3 7> 1 1 4
 3 3 <3 5> 1 2
 3 3 3 <3 3>
--------------- -----
 15

function processData(input) 
 var [length, ...values] = input.split(/\n

console.log(processData('5n1 4 2 7 1')); // 7
console.log(processData('5n7 4 2 1 1')); // 15
console.log(processData('3n1 2 3')); // 2

Your solution seems to be O(n^2) but should be solvable in O(n):

function processCandyArray(candies) 
 let sum = 0, steps = 0, carry = 0
 for (let i = 0; i < candies.length; i++)
 sum += candies[i]
 let avg = sum / candies.length
 for (let i = 0; i < candies.length - 1; i++) 
 carry = candies[i] + carry - avg
 steps += carry > 0 ? carry : -carry
 
 return steps

You can just go through the array after calculating the average and at each position you calculate how many candies are carried over (from the left is positive and from the right is negative carry) and sum up the absolute carries.