Buy Maximum Stocks | Editorial by aksingh007

This is a greedy problem, where you should start buying product from the day when the stock price is least, then second least and so on.
So, we will sort the pair of two values ie. {stock price, day} according to the stock price, and if stock prices are same, then we sort according to the day.
Now, we will traverse along the sorted list of pairs, and start buying as follows:
Let say, we have R dollar remaining till now, and the cost of product on this day be C, and we can buy atmost L products on this day then,
total purchase on this d**ay (P) = min(L , R / C)**
Now, add this value to the answer
**total_purchase = total_purchase + P**, where **P = min(L , R / C)**
Now, subtract the cost of buying P items from remaining money,
**R -= P * C**
Total number of products that we can buy is equal to total_purchase.

Code:Java8
```
import java.util.*;

class Pair implements Comparable<Pair>{
	long key,val;
	Pair(long key,long val){
		this.key=key;
		this.val=val;
	}
	public int compareTo(Pair p){
		return (int)(this.val-p.val);
	}
}

class Golds2{
	public static void main(String args[]){
		Scanner sc=new Scanner(System.in);
		long n=sc.nextLong();
		ArrayList<Pair> arr=new ArrayList<Pair>();
		for(long i=1;i<=n;i++)
			arr.add(new Pair(i,sc.nextLong()));
		Collections.sort(arr);
		//for(Pair x:arr)
			//System.out.println(x.val+"-"+x.key);
		long count=0;
		long sum=sc.nextLong();
		for(Pair x:arr){
			long k=x.key;
			long v=x.val;
			if(k*v<=sum){
				count+=k;
				sum=sum-k*v;
			}
			else
				if(k*v>sum){
					count+=sum/v;
					break;
				}
		}
		System.out.println(count);
	}
}
```

Buy Maximum Stocks | Editorial by aksingh007

Download submission

All caught up!

View submission

Is your resume even shortlisted?