Connection Status:
Competition Arena > TaroCoins

TaroCoins

SRM 631 · 2014-07-26 · by Witaliy

SRM 631 · 2014-07-26 · by Witaliy · Brute Force, Dynamic Programming
Class Name: TaroCoins
Return Type: long
Method Name: getNumber
Arg Types: (long long)
Problem Statement

Problem Statement

Cat Taro likes coins. For any non-negative integer K, he has exactly two coins of value 2^K (i.e., two to the power of K).

You are given a long N. Return the number of different ways Taro can represent the value N with coins that he has. (Two representations are considered different if there is a value that occurs a different number of times in the representations.)

Notes

  • The answer will always fit in a signed 64-bit integer.

Constraints

  • N will be between 1 and 1,000,000,000,000,000,000 (10^18), inclusive.
Examples
0)
1
Returns: 1

The only possible way to represent N in this case is to use one coin of value 1.

1)
6
Returns: 3

The following three representations are possible in this case: {1, 1, 2, 2}, {1, 1, 4} and {2, 4}

2)
47
Returns: 2
3)
256
Returns: 9
4)
8489289
Returns: 6853

Submissions are judged against all 63 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class TaroCoins with a public method long long getNumber(long long N) · 63 test cases · 2 s / 256 MB per case

Submitting as anonymous