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

Maximum Number of Operations With the Same Score I

Number: 3320

Difficulty: Easy

Paid? No

Companies: Microsoft

Problem Description

Given an integer array nums, you are allowed to perform the following operation repeatedly as long as there are at least two elements in the array: remove two numbers at a time and define the score of the operation as the sum of these two numbers. However, a requirement is imposed that the score should be identical for every operation performed. The task is to determine the maximum number of such operations (or, equivalently, the maximum number of pairs) that can be executed.

Key Insights

  • Forming an operation is equivalent to pairing two numbers whose sum equals some candidate score S.
  • All pairs (operations) must have the same sum S.
  • We can try every possible candidate sum S (from the minimum possible sum to the maximum possible sum) and compute the maximum disjoint pairs that can be formed with that sum.
  • A frequency count (or frequency map) of the numbers allows us to quickly compute the number of pairs available for each candidate sum. Special care is taken when the pair consists of two identical numbers.
  • The answer is the maximum number of pairs obtained over all candidate scores.

Space and Time Complexity

Time Complexity: O(range * k) where range is the possible sums (up to 2 * max(nums)) and k is the number of distinct numbers. In the worst-case, with nums.length up to 100 and nums[i] up to 1000, this approach is efficient. Space Complexity: O(n) due to the frequency map.

Solution

The solution involves:

  1. Counting the frequency of each element in nums.
  2. Iterating over every candidate sum S (from 2 to 2 * max(nums)) and for each candidate:
    • For each unique number x, check if there exists its complement (S - x).
    • If x is different from its complement, the number of pairs that can be formed is the minimum of the frequency of x and the frequency of (S - x).
    • If x is equal to its complement then the number of pairs is frequency of x divided by 2 (using floor division).
  3. Keeping track of the maximum number of pairs over all candidate sums.
  4. Returning that maximum as the solution.

Code Solutions

def max_operations(nums):
    # Count the frequency of each number in nums.
    frequency = {}
    for num in nums:
        frequency[num] = frequency.get(num, 0) + 1

    max_pairs = 0
    # Candidate sums range from 2 (smallest possible sum with numbers >= 1)
    # to 2 * max(nums) (largest possible sum).
    for target_sum in range(2, max(nums) * 2 + 1):
        current_pairs = 0
        # Iterate over sorted keys to ensure each pair is only counted once.
        for num in sorted(frequency.keys()):
            complement = target_sum - num
            if complement not in frequency:
                continue
            if num < complement:
                # Number of pairs is the minimum frequency of num and its complement.
                current_pairs += min(frequency[num], frequency[complement])
            elif num == complement:
                # When both numbers are the same, form floor(freq / 2) pairs.
                current_pairs += frequency[num] // 2
        max_pairs = max(max_pairs, current_pairs)
    return max_pairs

# Example usage:
print(max_operations([3,2,1,4,5]))  # Expected output: 2
← Back to All Questions