Statistics

Problem Statement for "TaroCoins"

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.)

Definition

Class:
TaroCoins
Method:
getNumber
Parameters:
long
Returns:
long
Method signature:
long getNumber(long N)
(be sure your method is public)

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

  1. 1

    Returns: 1

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

  2. 6

    Returns: 3

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

  3. 47

    Returns: 2

  4. 256

    Returns: 9

  5. 8489289

    Returns: 6853

  6. 1000000000

    Returns: 73411

  7. 100

    Returns: 19

  8. 128

    Returns: 8

  9. 1073741824

    Returns: 31

  10. 6370

    Returns: 175

  11. 10

    Returns: 5

  12. 2

    Returns: 2

  13. 3

    Returns: 1

  14. 4

    Returns: 3

  15. 2000000000

    Returns: 81034

  16. 999999999

    Returns: 7623

  17. 1000000000000000000

    Returns: 554817437

  18. 576460752303423488

    Returns: 60

  19. 640

    Returns: 23

  20. 785

    Returns: 34

  21. 1022

    Returns: 10

  22. 962

    Returns: 38

  23. 640

    Returns: 23

  24. 1099510542205

    Returns: 17863

  25. 944875173846

    Returns: 1243789

  26. 672031828383

    Returns: 500073

  27. 893915235088

    Returns: 243779

  28. 1088385987371

    Returns: 4634234

  29. 347905064087584832

    Returns: 5150282

  30. 309341003709448449

    Returns: 19102955

  31. 361431780114432130

    Returns: 94727263

  32. 378311177695920400

    Returns: 20702253

  33. 290553370434404484

    Returns: 146293655

  34. 423901414250789313

    Returns: 292614203

  35. 438190581230404958

    Returns: 6012372582

  36. 293666568548731467

    Returns: 3648043185

  37. 392393882169705920

    Returns: 3341296806

  38. 376370659955075108

    Returns: 3279511256

  39. 412658913555584867

    Returns: 3498747798

  40. 410054521552536292

    Returns: 26030230909

  41. 416860608518791589

    Returns: 8015276820

  42. 393014244375683364

    Returns: 16905456859

  43. 518010418436963490

    Returns: 15340957057

  44. 576460730781662959

    Returns: 794365

  45. 565764701561028461

    Returns: 2186952

  46. 571954850028252927

    Returns: 7287457

  47. 558161296277634687

    Returns: 1416255

  48. 504314853196816127

    Returns: 6183662

  49. 768614336404564650

    Returns: 2504730781961

  50. 384307168202282325

    Returns: 956722026041

  51. 384307168202282324

    Returns: 1548008755920

  52. 192153584101141162

    Returns: 956722026041

  53. 196657183728511722

    Returns: 502131822759

  54. 193349852752161450

    Returns: 484936992181

  55. 196731950519200426

    Returns: 350312970581

  56. 192153584101141166

    Returns: 644603021052

  57. 10000000000000000

    Returns: 17165857

  58. 200

    Returns: 26

  59. 93459834598323452

    Returns: 317400926

  60. 1717161617181871

    Returns: 69493195

  61. 123456789

    Returns: 51639

  62. 999999999999999999

    Returns: 29665503

  63. 263810380166378775

    Returns: 4693345949

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: