CareerCup

This is the approach I came up with. I'm unsure if it's the optimal solution though. Would love suggestions!

Anyways, the idea is that you evaluate each kid in the circle, if he can pass an apple to someone who needs it behind him, then he does. Otherwise, if they have excess apples, then they just continue to pass it forward.

From the way the question seemed to be phrased, I took it that a pass is a single iteration through all children in the circle, so once everyone has given an apple away (if they can), then the next pass (step) starts.

#include <iostream>
using namespace std;

struct Child {
    int AppleCount;

    Child( ) { AppleCount = 0; }
    Child( int appleCount ) { AppleCount = appleCount; }
};

// Returns false if there are no apples to pass, true otherwise
bool PassApples( Child* children, unsigned childCount, unsigned appleCount ) {

    // Check our kids and see if there are more apples to be passed on
    bool needsPass = false;
    unsigned endIdx = childCount - 1;
    for( unsigned i = 0; i < childCount; ++i ) {

        int prevChildIdx;

        if( i == 0 ) 
            prevChildIdx = childCount - 1;
        else
            prevChildIdx = i - 1;

        // If the child before us has less apples than desired, pass it to him
        if( children[ prevChildIdx ].AppleCount < appleCount && children[ i ].AppleCount ) {
            children[ prevChildIdx ].AppleCount += 1;
            children[ i ].AppleCount -= 1;
            needsPass = true;
        }
        else {
            // If this child has excess apples, pass it along.
            if( children[ i ].AppleCount > appleCount ) {
                children[ i ].AppleCount -= 1;
                children[ (i + 1) % childCount ].AppleCount += 1;
                needsPass = true;
            }
        }
    }
    
    return needsPass;
}

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

    // @TODO: Read the values in from input, or a file or something...
    const int CHILDCOUNT = 5;
    Child children[ CHILDCOUNT ] = { 3, 4, 6, 10, 2 };

    // Find total apples
    unsigned totalApples = 0;
    for( int i = 0; i < CHILDCOUNT; ++i )
        totalApples += children[ i ].AppleCount;

    bool needsPass = true;
    unsigned numPasses = 0;
    while( needsPass ) {
        if( PassApples( children, CHILDCOUNT, totalApples / CHILDCOUNT ) )
            ++numPasses;
        else
            needsPass = false;
    }

    cout << "Total Passes: " << numPasses;

    // This is just here so that the app doesn't close before output can be seen
    char c;
    cin >> c;
}

If we are allowed to sort the sequence then after sort we can distribute the one apple to its neighbors until everybody has same.

// Apple.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>

using namespace std;

void Pass(int arr[],int i,int N)
{
	if(i==0)
	{

		if(arr[N-1]<N)
		{
			++arr[N-1];
			--arr[i];
		}
		else
		{
			if(arr[i+1]<N)
			{
				++arr[i+1];
				--arr[i];

			}
			else
			{
				++arr[i+1];
				--arr[i];
			}
		}
	}

	if(i==(N-1))
	{

		if(arr[i-1]<N)
		{
			++arr[i-1];
			--arr[i];
		}
		else
		{
			if(arr[0]<N)
			{
				++arr[0];
				--arr[i];

			}
			else
			{
				++arr[0];
				--arr[i];
			}
		}
	}
	else
	{
		if(arr[i-1]<N)
		{
			++arr[i-1];
			--arr[i];
		}
		else
		{
			if(arr[i+1]<N)
			{
				++arr[i+1];
				--arr[i];

			}
			else
			{

				++arr[i+1];
				--arr[i];
			}
		}
	}

}
int _tmain(int argc, _TCHAR* argv[])
{
	int N=5;
	int arr[5]={3,4,6,10,2};
	int count=0;

	int flag=1;
	while(flag)
	{
		for(int i=0;i<N;i++)
		{
			if(arr[i]>N)
			{

				++count;

				Pass(arr,i,N);


			}
		}
		int j;
		for(j=0;j<N;j++)
		{
			if(arr[j]!=N)
			{
				flag=1;
				break;
			}
		}
		if(j==N)
			flag=0;
	}

	std::cout<<"Number of Passes"<<cout;

	return 0;
}

use dequeue insert (n/2) element in the queue after that we take element(n/2+1,n/2-1) similarly after that(n/2+2,n/2-2) until complete array in traverse
Condition to add element to the queue is first calculate the number of apples each person must have
n/2-x added from front end and n/2+x added from back end similarly
1 if first apples is greater than average then it remove the elements from queue until all the additional apples is consumed .
2. if apples is less than average then add element to the queue.
complexity = O(n)
Space complexity =O(n)

Its a variant of the problem to find the longest sub-array(circular) that adds up to zero. The array in question, then, would be a sequence of numbers such that, every number = number - (sum of all apples / number of boys).
The maximum number of steps would be = sum of all positive numbers in the subarray found from the modified array.( if you assume that multiple children handing over an apple to their neighbors as a single step).
e.g.: N = 3. and input array is [0,2,7] then modified array is [-3,-1, 4]. So the the guy on the right gave an apple to the guy on the left, guy in the middle gave an apple to guy on left at the same time and so on. so total steps = 4.

This problem is similar to BALIFE on SPOJ
See solution here GitHub/saurabhksingh/SPOJ-Code/blob/master/src/com/dev/saurabh/BALIFE.java

divide the group(circle) into two district and calculate the net flow needed between two districts, and then divide each district into two smaller districts and calculate the net flow between them and also update the net flow between the lager district. Keep doing this till we reach the smallest individual and then we know what should be the flow.

Suppose T is the total number of balls and T/N=X.
Build a graph where each node corresponds to a child which doesn't have X balls.
The edges of the graph are the distances between each pair children (in the shortest direction around the circle) where one child has more than X balls and the other less ten X balls (there are no edges between children that both have more than X balls, or less then X balls).

Now pick the shortest edge, and remove it from the graph. Add to the total cost the distance of the edge multiplied by the number of balls moved, which is the minimum number required to get at least one of the children to X balls (example: first child has X+2 balls, second child X-3 balls, so we move two balls from the first child to the second). Remove the child with X balls from the graph. Repeat for all edges in the graph.

Total time is O(E log E), where E=O(N^2) so it's O(N^2 log N).

"N boys are sitting in a circle ... number of the apples can be divided by N"

Zero :-) if each boy holds two apples.

1.Divide the circle into 2 groups of equal size if even, or one group can be 1 larger if odd.
2.Calculate the diff between 2 groups to make the average apples per child equal
3. do the same for each of the 2 groups until the number of children in the group goes down to one.
4. adds up diffs at different levels between groups, that is the answer: Minimum moves

public class NBoysCircle {

	public static void main(String[] args) {
		int[] array = {3,4,6,10,2};
		int sumOfArray = 3+4+6+10+2;
		int distribution = sumOfArray/5;
		
		array = recursiveDivideEqually(array.length, array, distribution);
		
		for(int i =0; i<array.length; i++) {
			System.out.println (array[i]+",");
		}
	}
	
	public static int[] recursiveDivideEqually(int totalCount, int[] array, int distribution) {
		
		boolean arrayModified = false;
		for(int i =0; i<totalCount; i++) {
			int nextIndex = 0;
			int previousIndex = 0;
			if(i == totalCount-1) {
				nextIndex = 0;
			}else {
				nextIndex = i+1;
			}
			if(i == 0) {
				previousIndex = totalCount-1;
			}else {
				previousIndex = i-1;
			}
			
			if(array[i] < distribution) {
				if(array[nextIndex] > distribution) {
					array[i] = array[i] + 1;
					array[nextIndex] = array[nextIndex] - 1;
					arrayModified = true;
				}else if(array[previousIndex] > distribution) {
					array[i] = array[i] + 1;
					array[previousIndex] = array[previousIndex] - 1;
					arrayModified = true;
				}else {
					array[i] = array[i] + 1;
					array[nextIndex] = array[nextIndex] - 1;
					arrayModified = true;
				}
			}else if (array[i] > distribution) {
				if(array[nextIndex] < distribution) {
					array[i] = array[i] - 1;
					array[nextIndex] = array[nextIndex] + 1;
					arrayModified = true;
				}else if(array[previousIndex] < distribution) {
					array[i] = array[i] - 1;
					array[previousIndex] = array[previousIndex] + 1;
					arrayModified = true;
				}
			}
		}
		if(arrayModified) {
			recursiveDivideEqually(totalCount, array, distribution);
		}
		return array;
	}

}

Note that for all applicable solutions( not necessarily the minimal one), they share the same property: the net flow for each child is invariant.
So two solutions differ from a flow whose net flow for each child vanishes, that is, a circumfluence like 1->1->...->1.
To find the minimal solution, just start from any initial solution, subtract a circumfluence from it, to minimize the difference between the number of positive edges and negative edges. The constant flow in the circumfluence is the median of the flows in the initial solution.

Take [5,0,0,0,0] as an example, an initial flow is [4,3,2,1,0], with 10 steps. subtract the circumfluence [2,2,2,2,2] from it, we get a flow [2,1,0,-1,-2], with 6 steps. This is the minimal solution since it has equal number of positive edges and negative edges: 2.
The time complexicity is O(n).

In the worst case, one boy has all the apples and distributes it around the circle, 1 at a time. So if N is even, in the worst case the number of passes around the circle would be:
Number of passes = N/2 + 2(N/2 - 1) + 2(N/2 - 2)..so on as long as N/2 - 2 > 0
If N is odd:
Number of passes = 2(N/2) + 2(N/2 - 1) + 2(N/2 - 2)..so on as long as N/2 - 2 > 0
"/" is the division operator.