Buy Maximum Stocks if ‘i’ stocks can be bought on ‘i-th’ day

Easy
0/40
Average time to solve is 10m
profile
Contributed by
2 upvotes
Asked in company
Nykaa

Problem statement

You are given an array ‘prices’ of a stock and a number ‘amount’. Each element of the array/list prices, ‘prices[i]’ represent the price of the stock on the ‘i-th’ day. Your task is to buy the maximum number of stocks in ‘amount’ money. Every stock has an infinite supply.

Rule to buy a stock: On the ‘i-th’ day you can buy at max ‘i’ a number of stock and ‘i’ is ‘1’ based.

For example: Given ‘prices = {10, 7, 19}’, and ‘amount = 45’.

Buy 1- stock on the first day, 2-stocks on the second day, and 1-stock on the third day, so the total investment amount is ‘1 * 10 + 2 * 7 + 1 * 19 = 10 + 14+ 19 = 43’ so you can buy ‘4’ stock in ‘amount =45’.

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains two space-separated integers ‘n’ and ‘amount’, where ‘n’ denotes the number of elements in the array ‘prices’.

The second line of each test case contains n space-separated integers denoting the elements of the array ‘prices’.
Output Format: 
For every test case, return the maximum number of stock that you can buy.

Output for each test case will be printed in a separate line.
Note: 
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraint : 
1 <= T <= 100
1 <= N <= 3000 
1 <= Amount <= 10^9 
1 <= prices[i] <= 10^9

Where ‘T’ represents the number of test cases, ‘N’ is the number of elements in array ‘prices’, ‘amount’ denotes an integer. ‘prices[i]’ represents the value of the number at ‘i’ position in ‘prices’.

Time Limit: 1 sec
Sample Input 1:
2
3 10
3 4 2  
2 5
2 1
Sample Output 1:
4
3
Explanation of sample input 1:
Test Case 1:

Given ‘prices = { 3, 4, 2 }’, and ‘amount = 10’.
Buy 1- stock on the first day, and 3-stock on the third day, so the total investment amount is ‘1*3 + 3*2 = 3+6 = 9’ so you can buy ‘4’ stock in ‘amount =10’.

Test Case 2:

Given ‘prices = { 2, 1 }’, and ‘amount = 5’.
Buy 1- stock on the first day, and 2-stock on the second day, so the total investment amount is ‘1*2 + 2*1 = 3’ so you can buy ‘3’ stock in ‘amount =5’.
Sample Input 2:
2
3 30
10 12 11
5 30
3 5 3 2 9
Sample Output 2:
2
10
Hint

Can we use a greedy approach to solve this problem?

Approaches (1)
Greedy Algorithm

The key idea observation here is that we should always buy stock with minimum price. Suppose the minimum stock price is ‘x’ and you can buy only ‘i’ number of stock in ‘k’ amount.

If k>= i*x then you can buy ‘i’ stock, remain amount ‘k- i*x’.

Else you can buy ‘k/x’ stocks and remain amount is ‘k- i*(k/x)’.

 

The algorithm will be -

  • Create a 2-d vector/list ‘stockPrice’. To store price of the stock at ‘i’ day and index of ‘i+1’.
  • Now for each ‘i’
    • Add ‘price[i], and i+1’ in stockPrice’.
  • Sort the 2-d vector according to price.
  • Use ‘numberOfStocks = 0’, to store the total stock which can buy in ‘amount’ money
  • Now for each ‘i’ from 0 to N - 1:
    • If ‘stockPrice[i][0] * stockPrice[i][1] >= amount’, then buy ‘stockPrice[i][1]’ number of stocks in
      • ‘numberOfStocks = numberOfStocks + stockPrice[i][1]’, ‘amount = amount - stockPrice[i][0] * stockPrice[i][1]’.
    • Else, you can’t buy all the stocks
      • ‘numberOfStocks = numberOfStocks+ amount / stockPrice[i][0]’,
      • ‘amount = amount - stockPrice[i][1]*(amount/stockPrice[i][0])’.
  • Return ‘numberOfStocks’

 

Time Complexity

O(N*log(N)), Where ‘N’ is the size of the given array ‘prices’.

 

Time complexity due to we are storing a vector/list of size ‘N’ in ‘N*log(N)’ time.

Space Complexity

O(N), Where ‘N’ is the size of the given array ‘prices’.

 

We are using an extra 2-d vector/list to store a pair of price and respective index.

Code Solution
(100% EXP penalty)
Buy Maximum Stocks if ‘i’ stocks can be bought on ‘i-th’ day
Full screen
Console