Minimum Cost of Buying Candies With Discount

🏠 ⬅️ ➡️

A shop is selling candies at a discount. For every two candies sold, the shop gives a third candy for free.

The customer can choose any candy to take away for free as long as the cost of the chosen candy is less than or equal to the minimum cost of the two candies bought.

  • For example, if there are 4 candies with costs 1, 2, 3, and 4, and the customer buys candies with costs 2 and 3, they can take the candy with cost 1 for free, but not the candy with cost 4.

Given a 0-indexed integer array cost, where cost[i] denotes the cost of the ith candy, return the minimum cost of buying all the candies.

Example 1:

Input: cost = [1,2,3] Output: 5 Explanation: We buy the candies with costs 2 and 3, and take the candy with cost 1 for free. The total cost of buying all candies is 2 + 3 = 5. This is the only way we can buy the candies. Note that we cannot buy candies with costs 1 and 3, and then take the candy with cost 2 for free. The cost of the free candy has to be less than or equal to the minimum cost of the purchased candies.

Example 2:

Input: cost = [6,5,7,9,2,2] Output: 23 Explanation: The way in which we can get the minimum cost is described below: - Buy candies with costs 9 and 7 - Take the candy with cost 6 for free - We buy candies with costs 5 and 2 - Take the last remaining candy with cost 2 for free Hence, the minimum cost to buy all candies is 9 + 7 + 5 + 2 = 23.

Example 3:

Input: cost = [5,5] Output: 10 Explanation: Since there are only 2 candies, we buy both of them. There is not a third candy we can take for free. Hence, the minimum cost to buy all candies is 5 + 5 = 10.

Constraints:

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

    integer :: i, j, k, n
    integer, parameter :: m = 100
    integer, dimension(m) :: cost
    integer :: min_cost

    ! read input
    read(*,*) n
    do i = 1, n
        read(*,*) cost(i)
    end do

    ! solve problem
    min_cost = solve(n, cost)

    ! print output
    write(*,*) min_cost

contains

    function solve(n, cost) result(min_cost)
        implicit none
        integer, intent(in) :: n
        integer, dimension(n), intent(in) :: cost
        integer :: i, j, k, l, min_cost
        logical :: found

        min_cost = huge(1_8)

        do i = 1, n - 1
            do j = i + 1, n
                do k = 1, n
                    if (k == i .or. k == j) cycle
                    if (cost(i) + cost(j) > cost(k)) cycle
                    found = .false.
                    do l = 1, n
                        if (l == i .or. l == j .or. l == k) cycle
                        if (cost(l) >= cost(k)) cycle
                        found = .true.
                        exit
                    end do
                    if (.not. found) then
                        min_cost = min(min_cost, cost(i) + cost(j) + cost(k))
                    end if
                end do
            end do
        end do

    end function solve

end program main
✅ Compiled
❌ Executed
❌ Correct 
program main
    implicit none
    integer, parameter :: n = 100
    integer :: cost(n)
    integer :: i, j, k
    integer :: total_cost

    ! read input
    read (*,*) cost

    ! initialize variables
    total_cost = 0

    ! loop through the candies
    do i = 1, size(cost)
        ! if the cost is less than or equal to the minimum cost of the two previous candies
        if (cost(i) <= total_cost) then
            ! take the candy for free
            total_cost = total_cost - cost(i)
        else
            ! add the cost of the candy to the total cost
            total_cost = total_cost + cost(i)
        end if
    end do

    ! print output
    write (*,*) total_cost
end program main
🌐 Data from online sources 
def max_difference(nums):
    min_val = nums[0]
    max_diff = -1

    for i in range(1, len(nums)):
        if nums[i] > min_val:
            max_diff = max(max_diff, nums[i] - min_val)
        else:
            min_val = nums[i]

    return max_diff

The algorithm iterates through the array while keeping track of the smallest value found so far (min_val). For each element in the array, it checks if the current value is greater than the min_val. If it is, it calculates the difference and updates the max_diff if the difference is greater than the current max_diff. If the current value is not greater than the min_val, the min_val is updated to the current value. The algorithm returns the max_diff found during the iteration. If no such i and j exist, the max_diff remains -1.

🌐 Data from online sources 
int maxDifference(vector<int>& nums) {
    int min_val = nums[0];
    int max_diff = -1;

    for (int i = 1; i < nums.size(); ++i) {
        if (nums[i] > min_val) {
            max_diff = max(max_diff, nums[i] - min_val);
        } else {
            min_val = nums[i];
        }
    }
    return max_diff;
}

The algorithm iterates through the array while keeping track of the smallest value found so far (min_val). For each element in the array, it checks if the current value is greater than the min_val. If it is, it calculates the difference and updates the max_diff if the difference is greater than the current max_diff. If the current value is not greater than the min_val, the min_val is updated to the current value. The algorithm returns the max_diff found during the iteration. If no such i and j exist, the max_diff remains -1.