Spend it All

Spend it All

FULLTIME

There is a budget and an array of n costs. Repeat the following process until budget is less than the minimum element in cost.

Process

Start at element 0 and work to n - 1 . At each element cost[i] :

  • If cost[i] <= budget , reduce budget by cost[i] and move to the next index. This is a purchase.
  • If cost[i] > budget , move to the next index.

    • The array is circular, so the next index after n - 1 is index 0. Continue until there is not enough budget to make a purchase.

    Determine how many purchases are made.


    Function Description

    Complete the function countPurchases in the editor below.

    countPurchases has the following parameters:

  • int cost[n] : the costs of all the items
  • long budget : the starting amount of the budget to be spent


    • Returns

  • long : the number of purchases


    Example 1 :

    Input: cost = [5, 8, 3], budget = 12
    Output: 3
    Explanation: Process:

  • Buy item 0 for 5 -> budget = 12 - 5 = 7.
  • Item 1 is too expensive, budget = 7.
  • Buy item 2 for 3, budget = 7 - 3 = 4.
  • Items 0 and 1 are too expensive, budget = 4.
  • Buy item 2 for 3, budget = 4 - 3 = 1.
  • Now budget = 1, and there are no more items that can be purchased.
  • Return 3, the number of items purchased.


    • Constraints:

  • 1 <= n <= 2*105
  • 1 <= cost[i] <= 109
  • 1 <= budget <= 105




    • Get one-to-one training from Google Facebook engineers

    Top-notch Professionals

    Learn from Facebook and Google senior engineers interviewed 100+ candidates.
    Most recent interview questions and system design topics gathered from aonecode alumnus.
    One-to-one online classes. Get feedbacks from real interviewers.

    Customized Private Class

    Already a coding expert? - Advance straight to hard interview topics of your interest.
    New to the ground? - Develop basic coding skills with your own designated mentor.
    Days before interview? - Focus on most important problems in target company question bank.

    Free Consultation
    7 * 24. Reply in 2 hours. Free Quote
    [email protected]