Statistics

Problem Statement for "NewOperator"

Problem Statement

Given a positive integer N, we may define the following unary functions:

  • sum(N) is the sum of the decimal digits of N.
  • prod(N) is the product of the decimal digits of N.
  • prod3(N) is the product of the three largest decimal digits of N.
    If N has less than three digits, prod3(N)=prod(N).
  • smallest(N) is the smallest decimal digit of N.
  • first(N) is the first (most significant) decimal digit of N.

Now we may define the binary operator @ as follows:

  • X@Y = 5 * prod3(X) + first(X) * sum(Y) + smallest(Y)

Examples:

  • sum(47) = 4+7 = 11
  • prod(2322) = 2*3*2*2 = 24
  • prod3(2322) = 3*2*2 = 12
  • prod3(47) = 4*7 = 28
  • smallest(427) = 2
  • first(427) = 4
  • 12034@217 = 5 * (4*3*2) + 1 * (2+1+7) + 1 = 131

We will be interested in expressions that use only the operator @ and a single variable x. Valid expressions are defined using the following rules:

  • x is a valid expression.
  • If E and F are valid expressions, then (E@F) is a valid expression.
  • Any string that can not be formed using the rules above is not a valid expression.

You are given an int x containing the value of the variable x used above, and an int goal. Find the shortest valid expression that evaluates to goal, and return the number of operators it contains. If no such expression exists, return -1 instead.

Definition

Class:
NewOperator
Method:
minimumCount
Parameters:
int, int
Returns:
int
Method signature:
int minimumCount(int x, int goal)
(be sure your method is public)

Constraints

  • x will be between 1 and 1,000,000, inclusive.
  • goal will be between 1 and 2,000,000,000, inclusive.

Examples

  1. 13

    13

    Returns: 0

    "x" is a valid expression that evaluates to 13.

  2. 374

    465

    Returns: 1

    "(x@x)" is a valid expression. For x=374 its value is 5 * (7*4*3) + 3 * (3+7+4) + 3 = 465.

  3. 374

    469

    Returns: 2

    "(x@(x@x))" evaluates to 469.

  4. 374

    659

    Returns: 2

    "((x@x)@x)" evaluates to 659. Note that the operator is not associative.

  5. 374

    1024

    Returns: 8

  6. 654321

    12

    Returns: 10

  7. 654321

    1234567

    Returns: -1

  8. 374

    664

    Returns: 3

  9. 374

    1160

    Returns: 5

  10. 999999

    4140

    Returns: 1

  11. 999999

    4139

    Returns: -1

  12. 999999

    4141

    Returns: -1

  13. 999989

    4130

    Returns: 1

  14. 999986

    4140

    Returns: -1

  15. 518150

    3327

    Returns: 91

  16. 511805

    3327

    Returns: 91

  17. 845521

    3706

    Returns: 62

  18. 443377

    3909

    Returns: 39

  19. 84507

    3834

    Returns: 32

  20. 4700

    44

    Returns: 1

  21. 470

    44

    Returns: 1

  22. 47

    44

    Returns: 8

  23. 929

    929

    Returns: 0

  24. 929

    992

    Returns: 1

  25. 41

    41

    Returns: 0

  26. 41

    3100

    Returns: -1

  27. 992

    929

    Returns: -1

  28. 992

    992

    Returns: 0

  29. 152152

    34642

    Returns: -1

  30. 325221

    364326

    Returns: -1

  31. 325232

    5235223

    Returns: -1

  32. 51244

    5325353

    Returns: -1

  33. 532254

    532523234

    Returns: -1

  34. 13344

    1987654321

    Returns: -1

  35. 654321

    654321

    Returns: 0

  36. 1000000

    1000000

    Returns: 0

  37. 289384

    2887

    Returns: 8

  38. 692778

    916

    Returns: 10

  39. 747794

    2336

    Returns: 7

  40. 885387

    493

    Returns: 7

  41. 516650

    1422

    Returns: 6

  42. 202363

    2028

    Returns: 18

  43. 368691

    60

    Returns: 6

  44. 897764

    1927

    Returns: 11

  45. 180541

    3427

    Returns: 34

  46. 89173

    3737

    Returns: 17

  47. 5212

    3369

    Returns: 21

  48. 702568

    430

    Returns: 10

  49. 465783

    1531

    Returns: 12

  50. 722863

    1124

    Returns: 12

  51. 174068

    3136

    Returns: -1

  52. 513930

    3803

    Returns: 21

  53. 634023

    3059

    Returns: 18

  54. 133070

    2168

    Returns: 18

  55. 961394

    2457

    Returns: 7

  56. 175012

    2043

    Returns: 11

  57. 176230

    1374

    Returns: 7

  58. 484422

    920

    Returns: 9

  59. 413785

    2538

    Returns: 15

  60. 575199

    2325

    Returns: 15

  61. 798316

    371

    Returns: 10

  62. 566414

    3527

    Returns: -1

  63. 776092

    981

    Returns: 13

  64. 759957

    1874

    Returns: 11

  65. 806863

    3171

    Returns: -1

  66. 906997

    1282

    Returns: 11

  67. 702306

    926

    Returns: 9

  68. 477085

    328

    Returns: 7

  69. 660337

    2506

    Returns: 16

  70. 750847

    1730

    Returns: 14

  71. 661314

    1858

    Returns: 12

  72. 616125

    1896

    Returns: 15

  73. 819583

    546

    Returns: 9

  74. 898815

    1368

    Returns: 10

  75. 515435

    2365

    Returns: 18

  76. 344044

    1751

    Returns: 12

  77. 1

    2000000000

    Returns: -1

  78. 4

    16

    Returns: 3

  79. 13

    4

    Returns: 3

  80. 731425

    137

    Returns: 8

  81. 1

    100000000

    Returns: -1

  82. 1

    2

    Returns: 5

  83. 10

    2000000000

    Returns: -1

  84. 654321

    12

    Returns: 10

  85. 1

    3000

    Returns: 18

  86. 654321

    123467

    Returns: -1

  87. 654321

    1234567

    Returns: -1

  88. 999

    998

    Returns: 11

  89. 26545

    352548

    Returns: -1

  90. 374

    1024

    Returns: 8

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: