Divide Array Into Equal Pairs

🏠 ⬅️ ➡️

You are given an integer array nums consisting of 2 * n integers.

You need to divide nums into n pairs such that:

  • Each element belongs to exactly one pair.
  • The elements present in a pair are equal.

Return true if nums can be divided into n pairs, otherwise return false.

Example 1:

Input: nums = [3,2,3,2,2,2] Output: true Explanation: There are 6 elements in nums, so they should be divided into 6 / 2 = 3 pairs. If nums is divided into the pairs (2, 2), (3, 3), and (2, 2), it will satisfy all the conditions.

Example 2:

Input: nums = [1,2,3,4] Output: false Explanation: There is no way to divide nums into 4 / 2 = 2 pairs such that the pairs satisfy every condition.

Constraints:

  • nums.length == 2 * n
  • 1 <= n <= 500
  • 1 <= nums[i] <= 500
Note: This problem is from LeetCode.
✅ Compiled
✅ Executed
✅ Correct 
program main
    implicit none

    integer, parameter :: n = 3
    integer, dimension(2*n) :: nums = [3,2,3,2,2,2]
    logical :: result

    result = canDividePairs(nums, n)
    print '(L1)', result

contains

logical function canDividePairs(nums, n)
    implicit none
    integer, intent(in) :: nums(:), n
    integer :: i, j

    canDividePairs = .true.

    do i = 1, size(nums), 2
        do j = i+1, size(nums), 2
            if (nums(i) /= nums(j)) then
                canDividePairs = .false.
                exit
            end if
        end do
        if (.not. canDividePairs) exit
    end do
end function canDividePairs

end program main
✅ Compiled
✅ Executed
❌ Correct 
module pairs
  implicit none
contains
  function can_divide(nums, n) result(res)
    integer, intent(in) :: nums(:), n
    logical :: res
    integer :: i, j, count

    res = .false.
    count = 0

    ! Iterate over the array and count the number of unique elements
    do i = 1, size(nums)
      count = count + 1
      do j = i + 1, size(nums)
        if (nums(i) == nums(j)) then
          count = count - 1
          exit
        end if
      end do
    end do

    ! If the number of unique elements is equal to n, then the array can be divided into n pairs
    if (count == n) then
      res = .true.
    end if
  end function can_divide
end module pairs

program main
  use pairs
  implicit none
  integer, parameter :: n = 3
  integer, parameter :: nums(2*n) = [3, 2, 3, 2, 2, 2]
  logical :: res

  res = can_divide(nums, n)
  if (res) then
    print *, "The array can be divided into ", n, " pairs."
  else
    print *, "The array cannot be divided into ", n, " pairs."
  end if
end program main
🌐 Data from online sources 
from typing import List

def max_bombs_detonated(bombs: List[List[int]]) -> int:
    n = len(bombs)
    max_bombs = 0

    for i in range(n):
        count = 0
        for j in range(n):
            dx = bombs[i][0] - bombs[j][0]
            dy = bombs[i][1] - bombs[j][1]
            distance = dx * dx + dy * dy
            range_ = bombs[i][2] * bombs[i][2] + bombs[j][2] * bombs[j][2]
            if distance <= range_:
                count += 1
        max_bombs = max(max_bombs, count)

    return max_bombs

To solve this problem, we want to find the maximum number of bombs that can be detonated by detonating a single bomb. The algorithm:
  1. Determine the number of bombs n and initialize a variable max_bombs to store the maximum number of bombs that can be detonated.
  2. Iterate through each bomb i in the given list of bombs.
  3. For each bomb, initialize a counter count to store the number of bombs it can detonate in its range.
  4. Iterate through all other bombs j.
    • Calculate the distance between the bombs i and j (using squared Euclidean distance to avoid floating point calculations).
    • Calculate the sum of the squares of the radii of bombs i and j.
    • If the distance between the bombs is less than or equal to the sum of the squares of their radii, it means bomb i can detonate bomb j. Increment the counter count.
  5. Update the maximum number of bombs that can be detonated by checking if count is greater than the current value of max_bombs.
  6. Repeat steps 3-5 for all bombs i.
  7. Return the value of max_bombs. This represents the maximum number of bombs that can be detonated by detonating a single bomb in the given list of bombs.
🌐 Data from online sources 
#include <vector>
#include <cmath>

int maxBombsDetonated(std::vector<std::vector<int>>& bombs) {
    int n = bombs.size();
    int max_bombs = 0;

    for (int i = 0; i < n; ++i) {
        int count = 0;
        for (int j = 0; j < n; ++j) {
            int dx = bombs[i][0] - bombs[j][0];
            int dy = bombs[i][1] - bombs[j][1];
            int distance = dx * dx + dy * dy;
            int range = bombs[i][2] * bombs[i][2] + bombs[j][2] * bombs[j][2];
            if (distance <= range) {
                count++;
            }
        }
        max_bombs = std::max(max_bombs, count);
    }

    return max_bombs;
}

To solve this problem, we want to find the maximum number of bombs that can be detonated by detonating a single bomb. The algorithm:
  1. Determine the number of bombs n and initialize a variable max_bombs to store the maximum number of bombs that can be detonated.
  2. Iterate through each bomb i in the given list of bombs.
  3. For each bomb, initialize a counter count to store the number of bombs it can detonate in its range.
  4. Iterate through all other bombs j.
    • Calculate the distance between the bombs i and j (using squared Euclidean distance to avoid floating point calculations).
    • Calculate the sum of the squares of the radii of bombs i and j.
    • If the distance between the bombs is less than or equal to the sum of the squares of their radii, it means bomb i can detonate bomb j. Increment the counter count.
  5. Update the maximum number of bombs that can be detonated by checking if count is greater than the current value of max_bombs.
  6. Repeat steps 3-5 for all bombs i.
  7. Return the value of max_bombs. This represents the maximum number of bombs that can be detonated by detonating a single bomb in the given list of bombs.