We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Operations to Make All Array Elements Equal

Number: 2718

Difficulty: Medium

Paid? No

Companies: Amazon, IBM, J.P. Morgan

Problem Description

Given an array of positive integers, nums, and multiple query values provided in the queries array, for each query you must determine the minimum number of operations needed to make all array elements equal to the query value. In one operation, you can increase or decrease an individual element by 1. After processing each query, the nums array is reset to its original state.

Key Insights

  • Sort the nums array to facilitate binary search.
  • Precompute a prefix sum array for efficient range sum queries.
  • For a given query (target value), use binary search to find the index where numbers become greater than the target.
  • Compute operations as the sum of differences for elements less than the target and those greater than the target.
  • Use the formula:
    • For left part (elements ≤ target): operations = target * count - prefix sum.
    • For right part (elements > target): operations = (prefix sum of right part) - target * (number of elements in right part).

Space and Time Complexity

Time Complexity: O(n log n + m log n)
Space Complexity: O(n)

Solution

We can solve the problem by first sorting the array and building a prefix sum array. For each query, we perform a binary search to split the array into two segments: elements less than or equal to the target and those greater than the target. Using the prefix sum, we calculate the cost to bring all elements in the left segment up to the target and the cost to bring all elements in the right segment down to the target. Summing these costs yields the minimum number of operations required for that query.

Code Solutions

Below are code solutions in Python, JavaScript, C++, and Java with line-by-line comments.

# Import bisect for binary search operations
import bisect

def minOperations(nums, queries):
    # Sort the input array to enable efficient binary searching
    nums.sort()
    n = len(nums)
    # Prepare prefix sum array; prefix[i] stores sum of first i elements (prefix[0] = 0)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + nums[i]
    
    result = []
    # Process each query
    for q in queries:
        # Find the insertion point where q would fit to maintain sorted order.
        idx = bisect.bisect_left(nums, q)
        # Operations for numbers less than q: increase them to q
        left_ops = q * idx - prefix[idx]
        # Operations for numbers greater than or equal to q: decrease them to q
        right_ops = (prefix[n] - prefix[idx]) - q * (n - idx)
        result.append(left_ops + right_ops)
    return result

# Example usage:
nums = [3, 1, 6, 8]
queries = [1, 5]
print(minOperations(nums, queries))  # Expected output: [14, 10]
← Back to All Questions