Maximum Number of Pairs in Array

🏠 ⬅️ ➡️

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
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer, parameter :: n = 8
    integer, dimension(n) :: nums
    integer, dimension(2) :: answer

    ! Example 1
    nums = [1, 3, 2, 1, 3, 2, 2]
    call solve(nums, answer)
    print '(A, I0, A, I0)', 'Example 1: ', answer(1), ' ', answer(2)

    ! Example 2
    nums = [1, 1]
    call solve(nums, answer)
    print '(A, I0, A, I0)', 'Example 2: ', answer(1), ' ', answer(2)

    ! Example 3
    nums = [0]
    call solve(nums, answer)
    print '(A, I0, A, I0)', 'Example 3: ', answer(1), ' ', answer(2)

contains

    subroutine solve(nums, answer)
        implicit none
        integer, dimension(:), intent(inout) :: nums
        integer, dimension(2), intent(out) :: answer
        integer :: i, j, count

        count = 0
        do while (any(nums == nums(1)))
            i = minloc(nums, dim=1, mask=(nums == nums(1)))[1]
            j = maxloc(nums, dim=1, mask=(nums == nums(1)))[1]
            if (i /= j) then
                nums(i) = -1
                nums(j) = -1
                count = count + 1
            end if
        end do
        answer(1) = count
        answer(2) = count(nums /= -1)
    end subroutine solve
end program main
❌ Compiled
❌ Executed
❌ Correct 
module pair_formation

implicit none

contains

function pair_formation_solution(nums) result(answer)

integer, intent(in) :: nums(:)
integer :: answer(2)

! Declare local variables
integer :: i, j, pairs, leftovers

! Initialize variables
pairs = 0
leftovers = 0

! Loop through the array and find pairs
do i = 1, size(nums) - 1
    do j = i + 1, size(nums)
        if (nums(i) == nums(j)) then
            pairs = pairs + 1
            leftovers = leftovers + 1
            nums(i) = -1
            nums(j) = -1
        end if
    end do
end do

! Remove any leftover numbers
do i = 1, size(nums)
    if (nums(i) /= -1) then
        leftovers = leftovers + 1
    end if
end do

! Assign the answer
answer = [pairs, leftovers]

end function pair_formation_solution

end module pair_formation

program pair_formation_test

use pair_formation

implicit none

! Test case 1
print *, pair_formation_solution([1, 3, 2, 1, 3, 2, 2])

! Test case 2
print *, pair_formation_solution([1, 1])

! Test case 3
print *, pair_formation_solution([0])

end program pair_formation_test
🌐 Data from online sources 
def count_pairs_leftovers(nums):
    counter = [0] * 101
    pairs, leftovers = 0, 0

    for n in nums:
        counter[n] += 1

    for count in counter:
        pairs += count // 2
        leftovers += count % 2

    return [pairs, leftovers]

The algorithm first initializes an array or hash map (in Java) to count the occurrences of each number in the given nums array. Then, it iterates through the input array nums and increments the count of each number.

After that, the algorithm iterates over the counter array or values (in Java, using .values()) and calculates the number of pairs and leftovers for each element. The number of pairs for an element is equal to the integer division of its count by 2 (count // 2 or count / 2), and the number of leftovers is equal to the count modulo 2 (count % 2).

Finally, the function returns an array containing the total number of pairs and leftovers.

🌐 Data from online sources 
#include <vector>
using namespace std;

vector<int> countPairsLeftovers(vector<int>& nums) {
    vector<int> counter(101, 0);
    int pairs = 0, leftovers = 0;

    for (int n : nums) {
        counter[n]++;
    }

    for (int count : counter) {
        pairs += count / 2;
        leftovers += count % 2;
    }

    return {pairs, leftovers};
}

The algorithm first initializes an array or hash map (in Java) to count the occurrences of each number in the given nums array. Then, it iterates through the input array nums and increments the count of each number.

After that, the algorithm iterates over the counter array or values (in Java, using .values()) and calculates the number of pairs and leftovers for each element. The number of pairs for an element is equal to the integer division of its count by 2 (count // 2 or count / 2), and the number of leftovers is equal to the count modulo 2 (count % 2).

Finally, the function returns an array containing the total number of pairs and leftovers.