DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’»

Cover image for Algorithms Problem Solving: Discount for prices
TK
TK

Posted on • Originally published at leandrotk.github.io

Algorithms Problem Solving: Discount for prices

This post is part of the Algorithms Problem Solving series.

Problem description

This is the Final Prices With a Special Discount in a Shop problem. The description looks like this:

Given the arrayΒ pricesΒ whereΒ prices[i]Β is the price of theΒ ithΒ item in a shop. There is a special discount for items in the shop, if you buy theΒ ithΒ item, then you will receive a discount equivalent toΒ prices[j]Β whereΒ jΒ is theΒ minimumΒ index such thatΒ j > iΒ andΒ prices[j] <= prices[i], otherwise, you will not receive any discount at all.

Return an array where theΒ ithΒ element is the final price you will pay for theΒ ithΒ item of the shop considering the special discount.

Examples

Input: prices = [8,4,6,2,3]
Output: [4,2,4,2,3]

Input: prices = [1,2,3,4,5]
Output: [1,2,3,4,5]

Input: prices = [10,1,1,6]
Output: [9,0,1,6]
Enter fullscreen mode Exit fullscreen mode

Solution

The solution idea is to iterate over the prices list and for each price, try to get a discount. If it has, apply the discount. Otherwise, the price stays the same.

I built a get_discount function passing the prices list, the index, and the current price.

To get the discount, we need to iterate through the list from the current index + 1 to the end of the prices list. If we find the first price that satisfies the rule, just return this price. If we didn't find any other price, just return 0.

Then we just need to apply the discount by subtracting the discount from the current price and add to the new list of prices with discount.

def final_prices(prices):
    result = []

    for index, price in enumerate(prices):
        discount = get_discount(prices, index, price)
        result.append(price - discount)

    return result

def get_discount(prices, index, price):
    for other_price in prices[index + 1:]:
        if other_price <= price:
            return other_price

    return 0
Enter fullscreen mode Exit fullscreen mode

We could also modify the prices list in-place.

Resources

Top comments (0)

πŸ‘‹ Welcome new DEV members in our Welcome Thread

Say hello to the newest members of DEV.