Maximum Product Difference Between Two Pairs

🏠 ⬅️ ➡️

The product difference between two pairs (a, b) and (c, d) is defined as (a * b) - (c * d).

  • For example, the product difference between (5, 6) and (2, 7) is (5 * 6) - (2 * 7) = 16.

Given an integer array nums, choose four distinct indices w, x, y, and z such that the product difference between pairs (nums[w], nums[x]) and (nums[y], nums[z]) is maximized.

Return the maximum such product difference.

Example 1:

Input: nums = [5,6,2,7,4] Output: 34 Explanation: We can choose indices 1 and 3 for the first pair (6, 7) and indices 2 and 4 for the second pair (2, 4). The product difference is (6 * 7) - (2 * 4) = 34.

Example 2:

Input: nums = [4,2,5,9,7,4,8] Output: 64 Explanation: We can choose indices 3 and 6 for the first pair (9, 8) and indices 1 and 5 for the second pair (2, 4). The product difference is (9 * 8) - (2 * 4) = 64.

Constraints:

  • 4 <= nums.length <= 104
  • 1 <= nums[i] <= 104
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    ! Solves the problem of finding the maximum product difference between two pairs of distinct indices in an array
    implicit none

    integer :: i, j, k, l, w, x, y, z
    integer :: a, b, c, d
    integer :: max_diff
    integer, dimension(100) :: nums

    ! Examples
    nums = reshape([5, 6, 2, 7, 4], shape=[5])
    write (*, '(A, I0)') 'Example 1: ', max_product_diff(nums)
    nums = reshape([4, 2, 5, 9, 7, 4, 8], shape=[7])
    write (*, '(A, I0)') 'Example 2: ', max_product_diff(nums)

contains

    function max_product_diff(nums) result(max_diff)
        ! Returns the maximum product difference between two pairs of distinct indices in an array
        implicit none
        integer, intent(in) :: nums(:)
        integer :: max_diff
        integer :: diff

        max_diff = 0
        do i = 1, size(nums) - 1
            do j = i + 1, size(nums)
                if (i /= j) then
                    a = nums(i)
                    b = nums(j)
                    do k = 1, size(nums)
                        if (k /= i .and. k /= j) then
                            c = nums(k)
                            do l = 1, size(nums)
                                if (l /= i .and. l /= j .and. l /= k) then
                                    d = nums(l)
                                    diff = (a * b) - (c * d)
                                    if (diff > max_diff) then
                                        max_diff = diff
                                        w = i
                                        x = j
                                        y = k
                                        z = l
                                    end if
                                end if
                            end do
                        end if
                    end do
                end if
            end do
        end do
        write (*, '(A, I0)') 'Maximum product difference: ', max_diff
        write (*, '(A, I0, A, I0, A, I0, A, I0)') 'Indices: ', w, ', ', x, ', ', y, ', ', z
    end function max_product_diff
end program main
❌ Compiled
❌ Executed
❌ Correct 
module max_product_difference

implicit none

contains

function max_product_difference(nums) result(max_diff)

integer, intent(in) :: nums(:)
integer :: max_diff, w, x, y, z, a, b, c, d

max_diff = -1

do w = 1, size(nums) - 3
    do x = w + 1, size(nums) - 2
        do y = x + 1, size(nums) - 1
            do z = y + 1, size(nums)
                a = nums(w)
                b = nums(x)
                c = nums(y)
                d = nums(z)
                if (a /= b .and. a /= c .and. a /= d .and. b /= c .and. b /= d .and. c /= d) then
                    max_diff = max(max_diff, (a * b) - (c * d))
                end if
            end do
        end do
    end do
end do

end function max_product_difference

end module max_product_difference

program test

use max_product_difference

implicit none

integer :: nums(4)
integer :: max_diff

nums = [5, 6, 2, 7]
max_diff = max_product_difference(nums)
write (*,*) "Max product difference: ", max_diff

nums = [4, 2, 5, 9, 7, 4, 8]
max_diff = max_product_difference(nums)
write (*,*) "Max product difference: ", max_diff

end program test
🌐 Data from online sources 
def min_changes(nums, k):
    n = len(nums)
    xor_prefix = [0] * (n + 1)
    for i in range(1, n + 1):
        xor_prefix[i] = xor_prefix[i - 1] ^ nums[i - 1]

    dp = [{} for _ in range(k)]
    min_dp = [n] * k

    for i in range(1, n + 1):
        x = xor_prefix[i] ^ xor_prefix[i - k]

        if i >= k:
            dp[0][x] = dp[0].get(x, 0) + 1

        for j in range(1, 1 + (i - j * k) // k):
            if x in dp[j - 1]:
                dp[j][x] = dp[j].get(x, 0) + 1
                min_dp[j] = min(min_dp[j], dp[j - 1][x] - dp[j][x])

    return min(n, [min_dp[j] + j for j in range(k)])

We first create a prefix XOR array called xor_prefix, containing the XOR values from the start of the original input array nums to each element in xor_prefix. We then initialize our dynamic programming table dp, which is an array of maps, and an array min_dp, that will be used to store the minimum elements to change.

We iterate through the prefix XOR array, calculating the XOR of the prefixes considering the length of k, and we store the count of the occurrences where the XOR is equal to zero.

For each possible combination of segment size and occurrences, we update our dp table and the min_dp array accordingly.

Finally, we iterate through the min_dp array to find the minimum number of elements to change, implying that the XOR of all segments is equal to zero. We return the minimum value found.

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

int minChanges(std::vector<int>& nums, int k) {
    int n = nums.size();
    std::vector<int> xor_prefix(n+1);
    for (int i = 1; i <= n; ++i) {
        xor_prefix[i] = xor_prefix[i-1] ^ nums[i-1];
    }

    std::vector<std::unordered_map<int, int>> dp(k);
    std::vector<int> min_dp(k, n);

    for (int i = 1; i <= n; ++i) {
        int x = xor_prefix[i] ^ xor_prefix[i - k];

        if (i >= k) {
            dp[0][x]++;
        }

        for (int j = 1; i - j * k >= 0; ++j) {
            dp[j][x]++;
            min_dp[j] = std::min(min_dp[j], dp[j-1][x] - dp[j][x]);
        }
    }

    int answer = n;
    for (int j = 0; j < k; ++j) {
        answer = std::min(answer, min_dp[j] + j);
    }
    return answer;
}

We first create a prefix XOR array called xor_prefix, containing the XOR values from the start of the original input array nums to each element in xor_prefix. We then initialize our dynamic programming table dp, which is an array of maps, and an array min_dp, that will be used to store the minimum elements to change.

We iterate through the prefix XOR array, calculating the XOR of the prefixes considering the length of k, and we store the count of the occurrences where the XOR is equal to zero.

For each possible combination of segment size and occurrences, we update our dp table and the min_dp array accordingly.

Finally, we iterate through the min_dp array to find the minimum number of elements to change, implying that the XOR of all segments is equal to zero. We return the minimum value found.