{"id":8255,"date":"2021-03-20T09:36:52","date_gmt":"2021-03-20T16:36:52","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8255"},"modified":"2021-03-20T09:38:04","modified_gmt":"2021-03-20T16:38:04","slug":"leetcode-1798-maximum-number-of-consecutive-values-you-can-make","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/greedy\/leetcode-1798-maximum-number-of-consecutive-values-you-can-make\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1798. Maximum Number of Consecutive Values You Can Make"},"content":{"rendered":"\n

You are given an integer array coins<\/code> of length n<\/code> which represents the n<\/code> coins that you own. The value of the ith<\/sup><\/code> coin is coins[i]<\/code>. You can make<\/strong> some value x<\/code> if you can choose some of your n<\/code> coins such that their values sum up to x<\/code>.<\/p>\n\n\n\n

Return the maximum number of consecutive integer values that you can<\/strong> make<\/strong> with your coins starting<\/strong> from and including<\/strong> <\/em>0<\/code>.<\/p>\n\n\n\n

Note that you may have multiple coins of the same value.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input:<\/strong> coins = [1,3]\nOutput:<\/strong> 2\nExplanation: <\/strong>You can make the following values:\n- 0: take []\n- 1: take [1]\nYou can make 2 consecutive integer values starting from 0.<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> coins = [1,1,1,4]\nOutput:<\/strong> 8\nExplanation: <\/strong>You can make the following values:\n- 0: take []\n- 1: take [1]\n- 2: take [1,1]\n- 3: take [1,1,1]\n- 4: take [4]\n- 5: take [4,1]\n- 6: take [4,1,1]\n- 7: take [4,1,1,1]\nYou can make 8 consecutive integer values starting from 0.<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> nums = [1,4,10,3,1]\nOutput:<\/strong> 20<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • coins.length == n<\/code><\/li>
  • 1 <= n <= 4 * 104<\/sup><\/code><\/li>
  • 1 <= coins[i] <= 4 * 104<\/sup><\/code>
    <\/li><\/ul>\n\n\n\n
    Solution: Greedy + Math<\/strong><\/h2>\n\n\n\n
    We want to start with smaller values, sort input array in ascending order.<\/p>\n\n\n\n
    First of all, the first number has to be 1 in order to generate sum of 1.
    Assuming the first i numbers can generate 0 ~ k.
    Then the i+1-th number x can be used if and only if x <= k + 1, such that we can have a consecutive sum of k + 1 by adding x to a sum between [0, k] and the new maximum sum we have will be k + x.<\/p>\n\n\n\n
    Time complexity: O(nlogn)
    Space complexity: O(1)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int getMaximumConsecutive(vector& coins) {\n    sort(begin(coins), end(coins));\n    int ans = 0;\n    for (int c : coins) {      \n      if (c > ans + 1) break;\n      ans += c;\n    }\n    return ans + 1;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    You are given an integer array coins of length n which represents the n coins that you own. The value of the ith coin is coins[i]. You can make some value x if you can choose some of…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[51],"tags":[88,31,177],"class_list":["post-8255","post","type-post","status-publish","format-standard","hentry","category-greedy","tag-greedy","tag-math","tag-medium","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8255","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=8255"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8255\/revisions"}],"predecessor-version":[{"id":8258,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8255\/revisions\/8258"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8255"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8255"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8255"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}