Two Sum Less Than K

🏠 ⬅️ ➡️

Given an array nums of integers and integer k, return the maximum sum such that there exists i < j with nums[i] + nums[j] = sum and sum < k. If no i, j exist satisfying this equation, return -1.

Example 1:

Input: nums = [34,23,1,24,75,33,54,8], k = 60 Output: 58 Explanation: We can use 34 and 24 to sum 58 which is less than 60.

Example 2:

Input: nums = [10,20,30], k = 15 Output: -1 Explanation: In this case it is not possible to get a pair sum less that 15.

Constraints:

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

    integer, parameter :: n = 9
    integer, parameter :: k = 60
    integer, dimension(n) :: nums = (/ 34, 23, 1, 24, 75, 33, 54, 8 /)
    integer :: i, j, sum

    do i = 1, n-1
        do j = i+1, n
            if (nums(i) + nums(j) == k) then
                write (*, '(A, I0, A, I0, A)') 'Found ', nums(i), ' + ', nums(j), ' = ', k
                exit
            end if
        end do
    end do

end program main
❌ Compiled
❌ Executed
❌ Correct 
module MaximumPairSum
    implicit none
    private
    public :: maximum_pair_sum
contains
    function maximum_pair_sum(nums, k) result(sum)
        integer, intent(in) :: nums(:)
        integer, intent(in) :: k
        integer :: sum
        integer :: i, j

        sum = -1
        do i = 1, size(nums) - 1
            do j = i + 1, size(nums)
                if (nums(i) + nums(j) == k) then
                    sum = k
                    exit
                elseif (nums(i) + nums(j) < k) then
                    sum = nums(i) + nums(j)
                end if
            end do
        end do
    end function maximum_pair_sum
end module MaximumPairSum

program test_maximum_pair_sum
    use MaximumPairSum
    implicit none
    integer, parameter :: nums = [34, 23, 1, 24, 75, 33, 54, 8]
    integer, parameter :: k = 60
    integer :: sum

    sum = maximum_pair_sum(nums, k)
    write (*,*) 'Maximum pair sum:', sum

    sum = maximum_pair_sum([10, 20, 30], 15)
    write (*,*) 'Maximum pair sum:', sum
end program test_maximum_pair_sum
🌐 Data from online sources 
def max_sum_under_k(nums, k):
    max_sum = -1
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            _sum = nums[i] + nums[j]
            if _sum < k and _sum > max_sum:
                max_sum = _sum
    return max_sum

The algorithm contains two nested loops, iterating through all possible combinations of indices i and j (with j > i). For each combination of i and j, the function calculates the sum of nums[i] and nums[j]. If the sum is less than k and greater than the current maxSum, the function updates maxSum with the new sum. Finally, the function returns the maximum sum found during the iterations. If no suitable sum was found, the function returns -1.

🌐 Data from online sources 
int maxSumUnderK(vector<int>& nums, int k) {
    int maxSum = -1;
    for (int i = 0; i < nums.size(); i++) {
        for (int j = i + 1; j < nums.size(); j++) {
            int sum = nums[i] + nums[j];
            if (sum < k && sum > maxSum) {
                maxSum = sum;
            }
        }
    }
    return maxSum;
}

The algorithm contains two nested loops, iterating through all possible combinations of indices i and j (with j > i). For each combination of i and j, the function calculates the sum of nums[i] and nums[j]. If the sum is less than k and greater than the current maxSum, the function updates maxSum with the new sum. Finally, the function returns the maximum sum found during the iterations. If no suitable sum was found, the function returns -1.