Minimum Average Difference LeetCode Solution

Problem – Minimum Average Difference LeetCode Solution

You are given a 0-indexed integer array nums of length n.

The average difference of the index i is the absolute difference between the average of the first i + 1 elements of nums and the average of the last n - i - 1 elements. Both averages should be rounded down to the nearest integer.

Return the index with the minimum average difference. If there are multiple such indices, return the smallest one.

Note:

  • The absolute difference of two numbers is the absolute value of their difference.
  • The average of n elements is the sum of the n elements divided (integer division) by n.
  • The average of 0 elements is considered to be 0.

Example 1:

Input: nums = [2,5,3,9,5,3]
Output: 3
Explanation:
- The average difference of index 0 is: |2 / 1 - (5 + 3 + 9 + 5 + 3) / 5| = |2 / 1 - 25 / 5| = |2 - 5| = 3.
- The average difference of index 1 is: |(2 + 5) / 2 - (3 + 9 + 5 + 3) / 4| = |7 / 2 - 20 / 4| = |3 - 5| = 2.
- The average difference of index 2 is: |(2 + 5 + 3) / 3 - (9 + 5 + 3) / 3| = |10 / 3 - 17 / 3| = |3 - 5| = 2.
- The average difference of index 3 is: |(2 + 5 + 3 + 9) / 4 - (5 + 3) / 2| = |19 / 4 - 8 / 2| = |4 - 4| = 0.
- The average difference of index 4 is: |(2 + 5 + 3 + 9 + 5) / 5 - 3 / 1| = |24 / 5 - 3 / 1| = |4 - 3| = 1.
- The average difference of index 5 is: |(2 + 5 + 3 + 9 + 5 + 3) / 6 - 0| = |27 / 6 - 0| = |4 - 0| = 4.
The average difference of index 3 is the minimum average difference so return 3.

Example 2:

Input: nums = [0]
Output: 0
Explanation:
The only index is 0 so return 0.
The average difference of index 0 is: |0 / 1 - 0| = |0 - 0| = 0.

Constraints:

  • 1 <= nums.length <= 105
  • 0 <= nums[i] <= 105

Minimum Average Difference LeetCode Solution in C++

class Solution {
public:
    int minimumAverageDifference(vector<int>& nums) {
        
        int n(size(nums)), minAverageDifference(INT_MAX), index;
        
        long long sumFromFront(0), sumFromEnd(0);
        for (auto& num : nums) sumFromEnd += num;
        
        for (int i=0; i<n; i++) {
            sumFromFront += nums[i];
            sumFromEnd -= nums[i];
            int a = sumFromFront / (i+1); // average of the first i + 1 elements.
            int b = (i == n-1) ? 0 : sumFromEnd / (n-i-1); // average of the last n - i - 1 elements.
            
            if (abs(a-b) < minAverageDifference) {
                minAverageDifference = abs(a-b);
                index = i;
            }
        }
        return index;
    }
};

Minimum Average Difference LeetCode Solution in Java

public int minimumAverageDifference(int[] nums) {
	int len = nums.length, res = 0;
	long min = Integer.MAX_VALUE, sum = 0, leftSum = 0, rightSum = 0;
	for (int num : nums)
		sum += num;
	for (int i = 0; i < len; i++) {
		leftSum += nums[i];
		rightSum = sum - leftSum;
		long diff = Math.abs(leftSum / (i + 1) - (len - i == 1 ? 0 : rightSum / (len -i - 1)));
		if (diff < min) {
			min = diff;
			res = i;
		}
	}
	return res;
}

Minimum Average Difference LeetCode Solution in Python

def minimumAverageDifference(self, nums: List[int]) -> int:
    n = len(nums)
    if n == 1:
        return 0

    queue = deque(nums[1: ])

    left_sum = sum(nums[0: 1])
    right_sum = sum(queue)

    left_length = 1
    right_length = n - 1

    i = 0

    min_avg = sys.maxsize
    min_avg_idx = None

    while i < n:
        left_avg = left_sum // left_length
        if right_length:
            right_avg = right_sum // right_length
        else:
            right_avg = 0

        diff = abs(left_avg - right_avg)
        if diff < min_avg:
            min_avg = diff
            min_avg_idx = i

        # if queue is empty, we can stop. as it is the end.
        if not queue:
            break
		# remove ele from left of the queue
        element = queue.popleft()

		# update for next iteration
        left_sum = left_sum + element
        right_sum = right_sum - element

        left_length += 1
        right_length -= 1

        i += 1

    return min_avg_idx
Minimum Average Difference LeetCode Solution Review:

In our experience, we suggest you solve this Minimum Average Difference LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Minimum Average Difference LeetCode Solution

Find on LeetCode

Conclusion:

I hope this Minimum Average Difference LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions

Leave a Reply

Your email address will not be published.