1 package com.shortthirdman.primekit.hackerearth;
2
3 import java.util.List;
4 import java.util.Objects;
5
6 /**
7 * Solves the optimal upgrade selection problem under a fixed currency constraint.
8 *
9 * <p>Each available upgrade index {@code i} incurs a given cost and yields an
10 * enhancement gain equal to {@code 2^i}[cite: 1]. Because every power of two is strictly greater
11 * than the sum of all preceding powers of two (i.e., {@code \sum_{j=0}^{i-1} 2^j = 2^i - 1 < 2^i}),
12 * the problem exhibits the greedy-choice property. This optimizer selects upgrades
13 * greedily starting from the highest available power down to zero.
14 *
15 * <p><strong>Thread Safety:</strong> This class is stateless, immutable, and thread-safe.
16 *
17 * @since 1.2.1
18 * @author ShortThirdMan
19 */
20 public class UpgradeEnhancementOptimizer {
21
22 private static final int MOD = 1_000_000_007;
23
24 /**
25 * Calculates the maximum enhancement obtainable without exceeding the provided budget.
26 *
27 * <p>Enhancement values grow exponentially such that the item at index {@code i}
28 * contributes {@code 2^i} enhancement[cite: 1]. The returned sum is reduced modulo {@code 10^9 + 7}[cite: 1].
29 *
30 * <h4>Algorithm Details</h4>
31 * <ul>
32 * <li><strong>Precomputes</strong> powers of two modulo {@code 1,000,000,007}.</li>
33 * <li><strong>Greedy Selection:</strong> Evaluates items in descending index order
34 * ({@code n - 1} down to {@code 0}), deducting the item cost whenever sufficient
35 * budget remains.</li>
36 * </ul>
37 *
38 * <h4>Complexity</h4>
39 * <ul>
40 * <li>Time Complexity: {@code O(n)}, where {@code n} is the size of {@code upgradeCosts}.</li>
41 * <li>Space Complexity: {@code O(n)} auxiliary memory for modular exponent precomputations.</li>
42 * </ul>
43 *
44 * @param upgradeCosts non-null list of non-negative integers representing upgrade costs,
45 * where element at index {@code i} yields enhancement {@code 2^i}[cite: 1]
46 * @param budget maximum spendable currency, must be non-negative
47 * @return the maximum enhancement score achievable within budget, modulo {@code 10^9 + 7}[cite: 1]
48 * @throws NullPointerException if {@code upgradeCosts} is {@code null}
49 * @throws IllegalArgumentException if {@code budget} is negative
50 */
51 public int optimizeInAppUpgrades(List<Integer> upgradeCosts, int budget) {
52 Objects.requireNonNull(upgradeCosts, "upgradeCosts must not be null");
53 if (budget < 0) {
54 throw new IllegalArgumentException("budget cannot be negative: " + budget);
55 }
56
57 int n = upgradeCosts.size();
58 if (n == 0) {
59 return 0;
60 }
61
62 // Precompute powers of 2: 2^0, 2^1, ..., 2^(n-1) modulo 10^9 + 7
63 int[] pow2 = new int[n];
64 pow2[0] = 1;
65 for (int i = 1; i < n; i++) {
66 pow2[i] = (pow2[i - 1] * 2) % MOD;
67 }
68
69 long remainingBudget = budget;
70 int totalEnhancement = 0;
71
72 for (int i = n - 1; i >= 0; i--) {
73 int cost = upgradeCosts.get(i);
74 if (remainingBudget >= cost) {
75 remainingBudget -= cost;
76 totalEnhancement += pow2[i];
77 if (totalEnhancement >= MOD) {
78 totalEnhancement -= MOD;
79 }
80 }
81 }
82
83 return totalEnhancement;
84 }
85 }