LeetCode in Kotlin

4014. Minimum Total Price After Applying Discounts

Medium

You are given two integer arrays prices and discounts.

The value prices[i] represents the price of the ith item, and discounts[j] represents a discount percentage.

You may apply discounts subject to the following rules:

If a discount of d percent is applied to an item with price p, its final price becomes (p * (100 - d)) / 100. The final price is not rounded.

Return the minimum possible sum of final prices after assigning discounts optimally. Answers within 10-5 of the actual answer will be accepted.

Example 1:

Input: prices = [10,30,21], discounts = [50,60]

Output: 32.50000

Explanation:

The total is 12 + 10.5 + 10 = 32.50000, which is the minimum possible.

Example 2:

Input: prices = [100,70], discounts = [10,40,50]

Output: 92.00000

Explanation:

The total is 50 + 42 = 92.00000, which is the minimum possible.

Example 3:

Input: prices = [7,3,9], discounts = [100,100]

Output: 3.00000

Explanation:

The total is 0 + 0 + 3 = 3.00000, which is the minimum possible.

Constraints:

Solution

class Solution {
    fun minPrice(prices: IntArray, discounts: IntArray): Double {
        val discount = IntArray(101)
        for (dis in discounts) {
            discount[dis]++
        }
        var maxprice = 0
        for (price in prices) {
            if (maxprice < price) {
                maxprice = price
            }
        }
        val price = IntArray(maxprice + 1)
        for (p in prices) {
            price[p]++
        }
        var ans = 0.0
        var i = pos(price, maxprice)
        var j = pos(discount, 100)
        while (i > 0) {
            ans += i - (i * j) / 100.0
            i = pos(price, i)
            j = pos(discount, j)
        }
        return ans
    }

    private fun pos(arr: IntArray, p: Int): Int {
        for (i in p downTo 1) {
            if (arr[i] > 0) {
                arr[i]--
                return i
            }
        }
        return 0
    }
}