Skip to content

3038. Maximum Number of Operations With the Same Score I

Description

You are given an array of integers nums. Consider the following operation:

  • Delete the first two elements nums and define the score of the operation as the sum of these two elements.

You can perform this operation until nums contains fewer than two elements. Additionally, the same score must be achieved in all operations.

Return the maximum number of operations you can perform.

 

Example 1:

Input: nums = [3,2,1,4,5]

Output: 2

Explanation:

  • We can perform the first operation with the score 3 + 2 = 5. After this operation, nums = [1,4,5].
  • We can perform the second operation as its score is 4 + 1 = 5, the same as the previous operation. After this operation, nums = [5].
  • As there are fewer than two elements, we can't perform more operations.

Example 2:

Input: nums = [1,5,3,3,4,1,3,2,2,3]

Output: 2

Explanation:

  • We can perform the first operation with the score 1 + 5 = 6. After this operation, nums = [3,3,4,1,3,2,2,3].
  • We can perform the second operation as its score is 3 + 3 = 6, the same as the previous operation. After this operation, nums = [4,1,3,2,2,3].
  • We cannot perform the next operation as its score is 4 + 1 = 5, which is different from the previous scores.

Example 3:

Input: nums = [5,3]

Output: 1

 

Constraints:

  • 2 <= nums.length <= 100
  • 1 <= nums[i] <= 1000

Solutions

Solution 1: Traversal

Thinking

Each operation takes the first two remaining numbers and must keep the first score. \(n \le 100\), so we simulate the rule.

The first sum \(s\) locks every later operation. We stop when fewer than two elements remain or the sum is not \(s\).

A scan with step \(2\) counts the operations.

First, we calculate the sum of the first two elements, denoted as \(s\). Then we traverse the array, taking two elements at a time. If their sum is not equal to \(s\), we stop the traversal. Finally, we return the number of operations performed.

The time complexity is \(O(n)\), where \(n\) is the length of the array \(nums\). The space complexity is \(O(1)\).

1
2
3
4
5
6
7
8
9
class Solution:
    def maxOperations(self, nums: List[int]) -> int:
        s = nums[0] + nums[1]
        ans, n = 0, len(nums)
        for i in range(0, n, 2):
            if i + 1 == n or nums[i] + nums[i + 1] != s:
                break
            ans += 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
    public int maxOperations(int[] nums) {
        int s = nums[0] + nums[1];
        int ans = 0, n = nums.length;
        for (int i = 0; i + 1 < n && nums[i] + nums[i + 1] == s; i += 2) {
            ++ans;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
public:
    int maxOperations(vector<int>& nums) {
        int s = nums[0] + nums[1];
        int ans = 0, n = nums.size();
        for (int i = 0; i + 1 < n && nums[i] + nums[i + 1] == s; i += 2) {
            ++ans;
        }
        return ans;
    }
};

1
2
3
4
5
6
7
func maxOperations(nums []int) (ans int) {
    s, n := nums[0]+nums[1], len(nums)
    for i := 0; i+1 < n && nums[i]+nums[i+1] == s; i += 2 {
        ans++
    }
    return
}

1
2
3
4
5
6
7
8
9
function maxOperations(nums: number[]): number {
    const s = nums[0] + nums[1];
    const n = nums.length;
    let ans = 0;
    for (let i = 0; i + 1 < n && nums[i] + nums[i + 1] === s; i += 2) {
        ++ans;
    }
    return ans;
}

Comments