Maximum Shares

Easy
0/40
Average time to solve is 30m
profile
Contributed by
13 upvotes
Asked in companies
WalmartFlipkart limited

Problem statement

You have recently read the biography of Warren Buffet and are very excited to start your investing journey. So, you have decided to buy shares of a certain company. Now, you have an initial capital of Rs ‘K’. You know the prices of the particular stock for the next ‘N’ days. On an ith day, you can buy up to i shares. To maximize the profit you want to buy a maximum number of shares, so find the maximum number of shares you can buy if you buy optimally.

Example:- 
Let, 
K = 45
N =3
PRICES = [10, 7, 19]
Answer:- 4
The answer should be 4 because you can purchase 1 stock on day 1,2 stocks on day 2 and 1 stock on day 3. Hence, total amount spent is 10*1 + 7*2 + 19*1 = 43 and number of stocks purchased is 4.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ representing the number of test cases. Then each test case follows.

The first line of each test case contains an integer ‘K’ denoting the initial capital you have.

The second line of each test case contains an integer ‘N’ denoting the number of days for which you know the price for the particular stock.

The third line contains ‘N’ integers of the array ‘PRICES’ denoting the price of the stock on an ith day.
Output Format : 
For each test case, print an integer denoting the maximum amount of stocks you can buy if you act in an optimal manner.

The output of each test case should be printed in a separate line.
Note : 
You are not required to print anything, it has already been taken care of. Just implement the function.
Constraints : 
1 <= T <= 5
 1 <= K <= 10^9
1 <= N <= 10^5
1 <= PRICES[i] <= 10^9

Time Limit = 1 sec
Sample Input 1 :
2
6
3
1 2 3
1
2
3 10
Sample Output 1 :
3
0
Explanation for Sample Output 1 :
In the first test case, the answer should be 3 because you can buy 1 share on the first day and 2 shares on the second day.
In the second test case, the answer should be 0 because you can’t buy any number of shares on any day.
Sample Input 2 :
1
100
3
7 10 4
Sample Output 2 :
6
Hint

Try to buy the maximum number of shares where the cost of the shares is less.

Approaches (1)
Greedy

We can observe that it is always optimal to buy shares on a day where the price is low. So, we can greedily start buying from the day where the price is the lowest.

 

 

 

Algorithm:-

 

 

  1. Initialize a variable named ANS to store the maximum number of shares that can be bought.
  2. Make an array named SHARES with PRICE[i] and the number of shares that can be bought on that day that is i plus i.
  3. Sort ‘SHARES’ according to the array ‘PRICE[i]’.
  4. Iterate from 0 to N.(Let’s say the iterator is i).
    1. If K is less than equal to 0, break.
    2. Else,
      1. Increment ANS by the minimum of SHARES[i][1] and K divided by SHARES[i][0].
      2. Decrement K by SHARES[i][0] multiplied by the minimum of SHARES[i][1] and K divided by SHARES[i][0].
  5. Return ANS.
Time Complexity

O(N * log N), where N is the number of days.

 

 

We are sorting the days by their buy prices, so the time complexity is O(N * log N).

Space Complexity

O(N), where N is the number of days.

 

We are using an auxiliary array to sort the days, so the space complexity is O(N).

Code Solution
(100% EXP penalty)
Maximum Shares
Full screen
Console