Identify the Coin Value to Avoid Arrest: N, K, S Problem

In a country some special kinds of coins are available. The coin’s value is decided by a rule, that the values of the coins are first N positive odd numbers. As an example, if N = 3 then coins consisting values are [1,2,5].

For quality, the country decided that every people should have exactly one coin of each type. If someone has more than one coin of each type, then the person will be arrested.

A businessman has a total S amount of money. He knows that he has one number of coin of each type except one. He has one type of coin exactly K times. Now the businessman asks you to find out which type of coin he has K times. So he can avoid arrest by donating money.

You are given N, K, S and you need to find out the value of the coin which appears K number times.

Example:

Input: 3 2 14
Output: 5

N = 3 so the available value of coins are [1,3,5]. So someone has at most 9 amount of money but the businessman has 14 amount of money, so he has one of the coin K numbers of times. The businessman coin values are [1,3,5,5] = 14. So he has the 5 value coin k number of times.

Input: 4 3 22
Output: 3

N = 4 so the available value of the coins are [1,3,5,7]. So someone has at most 16 amounts of money but the business has 22 amounts of money, so he has one of the coin K number of times. The businessman coin values are [1,3,3,3,5,7] = 22. He has the 3 value coin k number of times.

APPROACH:

The first step is to find the values of the coins in the country using N. We store the first N positive off numbers in an array. Now we need to calculate the maximum amount of money someone can get which is basically the sum of the array. Then we have the total amount of money the businessman has. Now if we traverse the coin value array and for each value, we calculate the total amount of money the businessman can have if he had this coin K number of times. If the amount and S matched then that will be the answer.

STEPS:

Calculate coin_val array using N.
Get the sum of the array
Traverse the array and check that how much money he can get if he has this value of coin K number of times
1. estimate = max_amount + coin_val[i] * (k-1)
If the estimate is equal to S then coin_cal[i] is present K number of times

SOLUTION:

def find_coin(n, k, s):
    coin_val = []
    count = 0
    i = 1
    # Storing the values of coins 
    while count &lt; n:
        coin_val.append(i)
        i += 2
        count += 1
        
    # maximum amount someone can get
    max_amount = sum(coin_val)
    for i in range(len(coin_val)):
      	# calculating estimate
        estimate = max_amount + coin_val[i] * (k - 1)
        if estimate == s:
            return coin_val[i]

# Main function
if __name__ =='__main__':
    n = 4
    k = 3
    s = 22
    res = find_coin(n, k, s)
    print(res)

Output

Time: O(n)
Space: O(n)