Codevita Previous Questions | Philand Coins

Philand Coins

LEVEL:Beginner

Description

The problem solvers have found a new Island for coding and named it as Philaland.These smart people were given a task to make purchase of items at the Island easier by distributing various coins with different value.Manish has come up with a solution that if we make coins category starting from $1 till the maximum price of item present on Island, then we can purchase any item easily. He added following example to prove his point.
Let's suppose the maximum price of an item is 5$ then we can make coins of {$1, $2, $3, $4, $5}to purchase any item ranging from $1 till $5.
Now Manisha, being a keen observer suggested that we could actually minimize the number of coins required and gave following distribution {$1, $2, $3}. According to him any item can be purchased one time ranging from $1 to $5. Everyone was impressed with both of them.Your task is to help Manisha come up with minimum number of denominations for any arbitrary max price in Philaland.

Input Format

First line contains an integer T denoting the number of test cases.
Next T lines contains an integer N denoting the maximum price of the item present Philaland.
Constraints
1<=T<=100
1<=N<=5000

Output Format

For each test case print a single line denoting the minimum number of denominations of coins required.

Example 1:

Input

2
10
5

Output

4 
3

Example 2:

Input

2
16
8

Output

5
4

Example 3:

Input

1
16

Output

Approach

To reach 10 the minimum way is every time divide by 2 until the value get 0.
i.e, 10/2=5---1 coin
5/2=2----1 coin
2/2=1----1 coin
1/2=0----1 coin
This can be done in two ways
1st way: rotating a loop until the number becomes 0 in every rotation we will divide the number with 2 and incrementing the count value.
Time complexity:O(n)
2nd way: Since the above example is in exponential form of 2 we can apply log function here
Time complextiy:O(1)

Note :

Let us know if you can come up with a better approach, mail us at support@theinquisitive.in Your approach will be reviewed and posted with credits to you.

Beginner

Philand Coins

LEVEL:Beginner

Description

Input Format

Output Format

Approach

Recommended Questions

Topic: Codevita Previous Questions

Beginner