Count Equal and Divisible Pairs in an Array

🏠 ⬅️ ➡️

Given a 0-indexed integer array nums of length n and an integer k, return the number of pairs (i, j) where 0 <= i < j < n, such that nums[i] == nums[j] and (i * j) is divisible by k.

Example 1:

Input: nums = [3,1,2,2,2,1,3], k = 2 Output: 4 Explanation: There are 4 pairs that meet all the requirements: - nums[0] == nums[6], and 0 * 6 == 0, which is divisible by 2. - nums[2] == nums[3], and 2 * 3 == 6, which is divisible by 2. - nums[2] == nums[4], and 2 * 4 == 8, which is divisible by 2. - nums[3] == nums[4], and 3 * 4 == 12, which is divisible by 2.

Example 2:

Input: nums = [1,2,3,4], k = 1 Output: 0 Explanation: Since no value in nums is repeated, there are no pairs (i,j) that meet all the requirements.

Constraints:

  • 1 <= nums.length <= 100
  • 1 <= nums[i], k <= 100
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer, parameter :: n = 7
    integer, parameter :: k = 2
    integer, dimension(n) :: nums
    integer :: i, j
    integer :: count

    ! Example 1
    nums = [3, 1, 2, 2, 2, 1, 3]
    write (*, '(A)') 'Example 1:'
    write (*, '(A)') 'Input: nums = [3,1,2,2,2,1,3], k = 2'
    write (*, '(A)') 'Output: ', solve(nums, k)
    write (*, '(A)') 'Expected: 4'

    ! Example 2
    nums = [1, 2, 3, 4]
    write (*, '(A)') 'Example 2:'
    write (*, '(A)') 'Input: nums = [1,2,3,4], k = 1'
    write (*, '(A)') 'Output: ', solve(nums, k)
    write (*, '(A)') 'Expected: 0'

contains

    function solve(nums, k) result(count)
        implicit none
        integer, intent(in) :: nums(:), k
        integer :: count
        integer :: i, j

        count = 0
        do i = 1, size(nums) - 1
            do j = i + 1, size(nums)
                if (nums(i) == nums(j)) then
                    if (mod((i - 1) * j, k) == 0) then
                        count = count + 1
                    end if
                end if
            end do
        end do
    end function solve

end program main
❌ Compiled
❌ Executed
❌ Correct 
module pair_with_divisible_product
    implicit none
    private
    public :: pair_with_divisible_product
contains
    subroutine pair_with_divisible_product(nums, k, result)
        integer, intent(in) :: nums(:)
        integer, intent(in) :: k
        integer, intent(out) :: result
        integer :: i, j, product

        result = 0
        do i = 1, size(nums) - 1
            do j = i + 1, size(nums)
                product = nums(i) * nums(j)
                if (product == k) then
                    result = result + 1
                end if
            end do
        end do
    end subroutine pair_with_divisible_product
end module pair_with_divisible_product

program test_pair_with_divisible_product
    use pair_with_divisible_product
    implicit none
    integer, parameter :: n = 7
    integer, parameter :: k = 2
    integer :: nums(n) = [3, 1, 2, 2, 2, 1, 3]
    integer :: result

    call pair_with_divisible_product(nums, k, result)
    write (*,*) "Result:", result

    nums = [1, 2, 3, 4]
    k = 1
    call pair_with_divisible_product(nums, k, result)
    write (*,*) "Result:", result
end program test_pair_with_divisible_product
🌐 Data from online sources 
def min_months(n, relations, time):
    order = [0] * n
    for r in relations:
        order[r[1] - 1] = max(order[r[1] - 1], r[0])
    totalTime = 0
    for i in range(n):
        totalTime = max(totalTime, time[i] + order[i])
    return totalTime

The algorithm starts by creating an array order to keep track of the maximum prerequisite course number for each course. For each relation, it updates the maximum prerequisite course number for the nextCourse with the prevCourse.

Next, go through each course, and calculate the total time needed to finish that course by adding the course's time plus the time of its maximum prerequisite course. Track the maximum time across all courses as totalTime.

Finally, return the maximum time totalTime as the minimum number of months needed to complete all courses.

🌐 Data from online sources 
#include <vector>
#include <algorithm>

int min_months(int n, std::vector<std::vector<int>>& relations, std::vector<int>& time) {
    std::vector<int> order(n, 0);
    for (auto& r : relations)
        order[r[1] - 1] = std::max(order[r[1] - 1], r[0]);
    int totalTime = 0;
    for (int i = 0; i < n; ++i)
        totalTime = std::max(totalTime, time[i] + order[i]);
    return totalTime;
}

The algorithm starts by creating an array order to keep track of the maximum prerequisite course number for each course. For each relation, it updates the maximum prerequisite course number for the nextCourse with the prevCourse.

Next, go through each course, and calculate the total time needed to finish that course by adding the course's time plus the time of its maximum prerequisite course. Track the maximum time across all courses as totalTime.

Finally, return the maximum time totalTime as the minimum number of months needed to complete all courses.