Below is the list and items of different items present at shop.

Name of Item price

Marble 1

Large Marble 2

Bouncing ball 4

Special bouncing ball 8

Rubber ball 16

Tennis ball 32

Season ball 64

Beach ball 128

Volley ball 256

Basket ball 512

Foot ball 1024

Special edition Foot ball 2048

Rahul has p amount of money with him.

Now he wants you to find the minimum number of items whose total price is exactly p.

Note that if Rahul buys the same item twice, then it is considered as two items are bought.

Testcases

10

256

511

4097

8194

Give the answer as multiplication of all answers.

Explanation

In the first sample, examples of the items whose total price is 10 are the following:

1+1+1+1+1+1+1+1+1+1 = 10 (10 item)

1+1+1+1+1+1+1+1+2 = 10 (9 items)

2+2+2+2+2 = 10 (5 items)

2+4+4 = 10 (3 items)

2+8 = 10 (2 items)

Here the minimum number of items is 2.

About scoring and submission

**Kunal Desai :** 7715051136**Neelraj Patil :** 9930671144

Privacy Policy