Statistics

Problem Statement for "TheLuckyBasesDivTwo"

Problem Statement

John and Brus believe that the digits 4 and 7 are lucky and all others are not.

Recently, they became interested in numeral systems with different bases. Normally, people use the numeral system with base 10 to represent numbers, however, there exist numeral systems with other bases. More exactly, for each integer B, B >= 2, there exists a numeral system with base B. In this system, there are B different digits, used to represent numbers from 0 to B-1, inclusive. In order to represent a positive integer A in such system, it's necessary to find such digits a[n], a[n-1], ..., a[0], that A = a[n] * B^n + a[n-1] * B^(n-1) + ... + a[0] * B^0 (here ^ denotes the power operator), and then write these digits from left to right, in this exact order. For example, 255 = 4 * 62 + 7, therefore representation of number 255 in the numeral system with base 62 consists of two digits, the leftmost digit is 4 and the rightmost digit is 7.

The base of numeral system B is called lucky for some integer number A if all digits of the number A represented in numeral system with base B are the lucky digits (i.e. 4 and 7). For example, base 62 is lucky for the number 255.

You are given a long n. Return the total number of lucky bases for the number n. If there are infinitely many such lucky bases, return -1 instead.

Definition

Class:
TheLuckyBasesDivTwo
Method:
find
Parameters:
long
Returns:
long
Method signature:
long find(long n)
(be sure your method is public)

Constraints

  • n will be between 1 and 10^12, inclusive.

Examples

  1. 255

    Returns: 1

    The only lucky base for the number 255 is 62. Note that base 52 is not lucky. Representation of 255 in this base contains digits 4 and 47. The digit 47 is not lucky, even though its decimal representation contains only lucky digits. Only the digits 4 and 7 are considered to be lucky.

  2. 4

    Returns: -1

    All bases greater than 4 are lucky.

  3. 13

    Returns: 0

    No lucky bases here.

  4. 60

    Returns: 2

  5. 17

    Returns: 0

  6. 23

    Returns: 0

  7. 52

    Returns: 1

  8. 347723696

    Returns: 1

  9. 925643275

    Returns: 2

  10. 65038986

    Returns: 0

  11. 644199585

    Returns: 0

  12. 333393417

    Returns: 1

  13. 255248223

    Returns: 1

  14. 683104052

    Returns: 1

  15. 517788483

    Returns: 1

  16. 434727064

    Returns: 1

  17. 610370488

    Returns: 2

  18. 454765462

    Returns: 1

  19. 643862778

    Returns: 0

  20. 852497597

    Returns: 1

  21. 619347723696

    Returns: 1

  22. 257925643275

    Returns: 1

  23. 120065038986

    Returns: 1

  24. 914644199585

    Returns: 1

  25. 912333393417

    Returns: 0

  26. 215255248223

    Returns: 1

  27. 191683104052

    Returns: 1

  28. 164517788483

    Returns: 1

  29. 493434727064

    Returns: 1

  30. 728610370488

    Returns: 2

  31. 919089952699

    Returns: 1

  32. 957759064442

    Returns: 0

  33. 919834457824

    Returns: 1

  34. 914618803015

    Returns: 1

  35. 912188536477

    Returns: 0

  36. 1000000000000

    Returns: 1

  37. 1

    Returns: 0

  38. 474747477747

    Returns: 3

  39. 747477474774

    Returns: 1

  40. 999999999048

    Returns: 1

  41. 999999999541

    Returns: 1

  42. 999999999973

    Returns: 0

  43. 999999999234

    Returns: 0

  44. 999999999667

    Returns: 2

  45. 999999999561

    Returns: 0

  46. 999999999245

    Returns: 0

  47. 999999999321

    Returns: 0

  48. 762939453124

    Returns: 2

  49. 141214768240

    Returns: 3

  50. 314146179364

    Returns: 2

  51. 854645986252

    Returns: 1

  52. 236663697847

    Returns: 2

  53. 549352360252

    Returns: 2

  54. 2044801603

    Returns: 2

  55. 254911373669

    Returns: 1

  56. 358759972685

    Returns: 1

  57. 99801488981

    Returns: 1

  58. 48853923508

    Returns: 2

  59. 920885238805

    Returns: 2

  60. 5695231426

    Returns: 1

  61. 156915327850

    Returns: 1

  62. 248176054407

    Returns: 2

  63. 60471954180

    Returns: 2

  64. 479064391809

    Returns: 1

  65. 124999994016

    Returns: 2

  66. 278013940

    Returns: 2

  67. 253706887

    Returns: 3

  68. 392716078000

    Returns: 2

  69. 468305010

    Returns: 1

  70. 123079338204

    Returns: 3

  71. 35016046314

    Returns: 2

  72. 34312041063

    Returns: 2

  73. 2782467538

    Returns: 2

  74. 26689021741

    Returns: 2

  75. 999998000004

    Returns: 2

  76. 9999887898

    Returns: 1

  77. 999999999999

    Returns: 2

  78. 44444444451

    Returns: 1

  79. 4000000004

    Returns: 2

  80. 99999999999

    Returns: 2

  81. 100000000000

    Returns: 1

  82. 99798999447

    Returns: 2

  83. 1000000000

    Returns: 1

  84. 2760721

    Returns: 1

  85. 47

    Returns: 1

  86. 4747

    Returns: 2

  87. 44

    Returns: 1

  88. 9999999019

    Returns: 1

  89. 156464699494

    Returns: 0

  90. 8

    Returns: 0

  91. 63

    Returns: 2

  92. 1684

    Returns: 4

  93. 532

    Returns: 3

  94. 744

    Returns: 2

  95. 100000000007

    Returns: 1

  96. 17048794

    Returns: 2

  97. 12345678901

    Returns: 0

  98. 14

    Returns: 0

  99. 77

    Returns: 1

  100. 4000008

    Returns: 1

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: