LeetCode in Kotlin

3946. Maximum Number of Items From Sale I

Medium

You are given a 2D integer array items, where items[i] = [factori, pricei] represents the ith item. You are also given an integer budget.

There are unlimited copies of each item available for purchase.You may buy any number of copies of any items such that the total cost of the purchased copies is at most budget.

After buying items, you may receive free copies according to the following rules:

• For each item i that you bought at least one copy of, you receive one free copy of every item j such that j != i and factori divides factorj.
• Buying multiple copies of the same item i does not give additional free copies through item i.
• The same item j can be received multiple times for free if it is received from purchases of different item types.

Return the maximum total number of item copies you can obtain, including both purchased copies and free copies, while spending at most budget on purchased items.

Example 1:

Input: items = [[6,2],[2,6],[3,4]], budget = 9

Output: 4

Explanation:

• You can buy 2 copies of item 0 and 1 copy of item 2 for a total cost of 2 * 2 + 4 = 8, which is not greater than budget = 9.
• Buying item 2 gives 1 free copy of item 0, because factor2 = 3 divides factor0 = 6.
• You leave with 3 purchased copies and 1 free copy, for a total of 4 item copies.

Example 2:

Input: items = [[2,4],[3,2],[4,1],[6,4],[12,4]], budget = 8

Output: 10

Explanation:

• You can buy 1 copy of item 0, 1 copy of item 1, and 2 copies of item 2 for a total cost of 4 + 2 + 2 * 1 = 8.
• Buying item 0 gives 1 free copy of items 2, 3, and 4.
• Buying item 1 gives 1 free copy of items 3 and 4.
• Buying item 2 gives 1 free copy of item 4.
• Thus, you receive 6 free copies. You leave with 4 purchased copies and 6 free copies, for a total of 10 item copies.

Constraints:

• 1 <= items.length <= 1000
• items[i] = [factori, pricei]
• 1 <= factori, pricei <= 1500
• 1 <= budget <= 1500

Solution

import kotlin.math.max
import kotlin.math.min

class Solution {
    fun maximumSaleItems(items: Array<IntArray>, budget: Int): Int {
        val n = items.size
        var maxFactor = 0
        var minPrice = Int.MAX_VALUE
        // Find the maximum factor (for our frequency array) and the minimum price
        for (item in items) {
            maxFactor = max(maxFactor, item[0])
            minPrice = min(minPrice, item[1])
        }
        // Count frequencies of each factor
        val freq = IntArray(maxFactor + 1)
        for (item in items) {
            freq[item[0]]++
        }
        // Precompute how many free items we get by buying at least 1 copy of item i
        val free = IntArray(n)
        for (i in 0..<n) {
            val f = items[i][0]
            var count = 0
            // Sum up the frequencies of all multiples of factor f
            var mult = f
            while (mult <= maxFactor) {
                count += freq[mult]
                mult += f
            }
            // Subtract 1 because we shouldn't count the item itself as a free copy
            free[i] = count - 1
        }
        // 0-1 Knapsack DP
        // dp[c] stores the max items we can get by spending exactly 'c' budget to activate items
        val dp = IntArray(budget + 1)
        dp.fill(-1)
        dp[0] = 0
        for (i in 0..<n) {
            val weight = items[i][1]
            val value = 1 + free[i]
            for (c in budget downTo weight) {
                if (dp[c - weight] != -1) {
                    dp[c] = max(dp[c], dp[c - weight] + value)
                }
            }
        }
        // Evaluate the best combination of activated items + leftover budget spent on cheapest
        // items
        var maxTotal = 0
        for (c in 0..budget) {
            if (dp[c] != -1) {
                // dp[c] gives us the activation items.
                // We buy the cheapest item repeatedly with the remaining budget.
                val currentTotal = dp[c] + (budget - c) / minPrice
                maxTotal = max(maxTotal, currentTotal)
            }
        }
        return maxTotal
    }
}

This site is open source. Improve this page.