CareerCup

So following Subbu's solution:

uint max_equal(int *a, uint n) {
    int s = 0;
    for (uint i = 0; i < n; i++) {
        s = (s + a[i])%n; // avoid overflow issues at slight cost of performance.
                                   // assumes % returns 0 to n-1.
    }
    return s==0 ? n : n-1;
}

We can always to n-1 (pick a dummy which absorbs +1 and -1 to make the others equal).

The key question is whether we can do n.

O(nk) where k is the number of possible candidates

private static int getBestAlign(int[] array) {
    // count number of elments that are equal - time: O(n)
    Integer value, min = Integer.MAX_VALUE, max = Integer.MIN_VALUE, maxCount = Integer.MIN_VALUE;
    for(int elem : array) {
      if(elem > max)
        max = elem;
      if(elem < min)
        min = elem;
    }

    // check each candidate - time O(nk) where k is the number of possible candidates 
    for(int candidate = min + 1; candidate < max; candidate++) {
      int sum = 0;
      for(int elem : array)
        sum += candidate - elem;
      if(sum == 0) {
        System.out.println("Candidate: " + candidate);
        return array.length;
      }
    }
    return array.length - 1;
  }

First sort the numbers. If there are 2 numbers then the minimal move is A[1] - A[0] by settling down the final number to any value between A[1] and A[0]. If there are 3 numbers, then the minimal move is A[3] - A[1]. by settling down the final number to A[2]. For N numbers the minimal moves is

(A[N-1]-A[0]) + (A[N-2]-A[1]) ...

temp = (a1+a2+a3+.......+an)%n;

ans will be max(temp,n-temp)

I think it is always able to make them equal except one case: # of elements are 2 and they are different.
We know that we can make at least (n-1) elements equal.
(a b c d .... -> a a (c-b) d .... -> a a a (d-(c-b)) ... something like this.)
As a result, 1st~(n-1)-th elements are same, but the n-th element is different.
Then, we can just increase/decrease 1st~(n-1)th elements until they are the value of the n-th element.

Hey guys, I did not get the question at all, can you explain it more?

public static void main(String[] args) throws Exception{
        Integer[] nArray = { 2, 5, 6, 3, 5, 5, 7, 2 };
        Collections.sort(Arrays.asList(nArray));
        Integer prevElement= nArray[0];
        Integer elementWithMostOccurrences = 0;
        Integer counter = 0;
        Integer maxCount =0;
        for(int i=0; j < nArray.length; j++) {
            if(nArray[i] == prevElement) {
                counter += 1;
            } else {
                if(counter > maxCount) {
                    maxCount = counter; 
                    elementWithMostOccurrences = nArray[i-1];
                }
                prevElement = nArray[i];
                counter = 1;
            }
        
        }
        
        System.out.println("Element which has most occurrences = "+elementWithMostOccurrences);
        System.out.println("Maximum number of elements that have same number = "+maxCount);
        
}

1) First you have to find a candidate to which ai and aj will be adjusted. To do this
count numbers and choose number which appears most often.
2) Take one number which is smaller then the candidate ai and one which is bigger aj and increment/decrements them respectively.
3) The result is equal candidate's number of occurrence + 2.
There is one border condition when the candidate is the biggest number in the array which means that you cant find aj to decrement. In that case you have to check if
'candidate's number of occurrence' - 'numOfOccurr of the secend most frequent number' >=1. Otherwise change the candidate to the second most frequent number.