2341. Maximum Number of Pairs in Array
Description
You are given a 0-indexed integer array nums
. In one operation, you may do the following:
- Choose two integers in
nums
that are equal. - Remove both integers from
nums
, forming a pair.
The operation is done on nums
as many times as possible.
Return a 0-indexed integer array answer
of size 2
where answer[0]
is the number of pairs that are formed and answer[1]
is the number of leftover integers in nums
after doing the operation as many times as possible.
Example 1:
Input: nums = [1,3,2,1,3,2,2] Output: [3,1] Explanation: Form a pair with nums[0] and nums[3] and remove them from nums. Now, nums = [3,2,3,2,2]. Form a pair with nums[0] and nums[2] and remove them from nums. Now, nums = [2,2,2]. Form a pair with nums[0] and nums[1] and remove them from nums. Now, nums = [2]. No more pairs can be formed. A total of 3 pairs have been formed, and there is 1 number leftover in nums.
Example 2:
Input: nums = [1,1] Output: [1,0] Explanation: Form a pair with nums[0] and nums[1] and remove them from nums. Now, nums = []. No more pairs can be formed. A total of 1 pair has been formed, and there are 0 numbers leftover in nums.
Example 3:
Input: nums = [0] Output: [0,1] Explanation: No pairs can be formed, and there is 1 number leftover in nums.
Constraints:
1 <= nums.length <= 100
0 <= nums[i] <= 100
Solutions
Solution 1: Counting
We can count the occurrences of each number $x$ in the array $\textit{nums}$ and record them in a hash table or array $\textit{cnt}$.
Then, we traverse $\textit{cnt}$. For each number $x$, if the occurrence count $v$ of $x$ is greater than $1$, we can select two $x$'s from the array to form a pair. We divide $v$ by $2$ and take the floor value to get the number of pairs that can be formed by the current number $x$. We then add this number to the variable $s$.
The remaining count is the length of the array $\textit{nums}$ minus the number of pairs formed multiplied by $2$, i.e., $n - s \times 2$.
The answer is $[s, n - s \times 2]$.
The time complexity is $O(n)$, and the space complexity is $O(C)$. Here, $n$ is the length of the array $\textit{nums}$, and $C$ is the range of numbers in the array $\textit{nums}$, which is $101$ in this problem.
1 2 3 4 5 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|