Android In-App Upgrades

Problem Statement

Android In-App Upgrades Description An Android app offers n in-app upgrades, numbered 0 to n - 1 . Upgrade i costs upgradeCosts[i] units of currency and enhances the app by 2^i . You have budget units of currency. Buy any set of upgrades whose total cost does not exceed the budget, so that the total enhancement -- the sum of 2^i over the upgrades you bought -- is as large as possible. Report that largest total enhancement **modulo 10^9 + 7 **. Complete the function optimizeInAppUpgrades in the editor below. Function Signature int optimizeInAppUpgrades(vector<int> upgradeCosts, int budget); Input The input is read from standard input as whitespace-separated integers, in this order: n , the number of upgrades. n integers, one per line, the array upgradeCosts . budget , the currency available. Output Print a single integer: the maximum total enhancement, reduced modulo 10^9 + 7 . Examples Example 1 Input: 5 10 20 14 40 50 70 Output: 20 Explanation: Buying upgrades 4 and 2 costs 50 +