4.2 Ryn Blackwood’s Adventure: Counting Coins
Ryn Blackwood stuffed all her coins from Hallway of Gold in a leather bag and set out to find a place to set camp for the night. Tent set up and fire burning, she sits down to rest and examines the coins and finds the coins are all of different sizes, each bearing a number.
After examining several coins, She discovered that the number on each coin indicates the total count of coins in the bag that have the same size. Exhausted from the day's exploration, Ryn decided to randomly select 'n' coins from the bag, record the numbers written on these coins in a list called 'marks' and make a minimum estimate for her report.
Help Ryn find the minimum number of possible coins in the bag according to his randomly selected sample.
Constraints
0<=n<=2.10^5
1<=marks[i]<=2.10^5
Input Format
The number of coins in the sample size ‘n’ followed by ‘n’ space separated numbers signifying the numbers on all ‘n’ coins
Output Format
Minimum number of possible coins in the bag
Example 1
Input:
3
2 2 3
Output:
5
Explanation:
The two coins that say 2 can be referring to each other. The third coin which says 3 indicates that there are two other coins like that.
2 + 3 = 5
Log In to solve the Question