Statistics

Problem Statement for "ILike5"

Problem Statement

You have certainly seen many tasks that start with some ridiculous made-up story. Well, this one is nothing like that.

Ivan A. is a smart boy. He just got a sequence of nonnegative integers as a birthday present. You are given this sequence in the int[] X.

Ivan A. adores the number 5. He thinks that a sequence is pretty if the product of all its elements ends with the digit 5. He now wants to change X into a pretty sequence. In each step he can choose an element of X and replace one of its digits by any other digit. For example, in a single step Ivan A. can change the number 1234 into the number 1734.

Compute and return the minimal number of steps needed to change X into a pretty sequence.

Definition

Class:
ILike5
Method:
transformTheSequence
Parameters:
int[]
Returns:
int
Method signature:
int transformTheSequence(int[] X)
(be sure your method is public)

Notes

  • It can be shown that any sequence X can be transformed into a pretty sequence in finitely many steps.
  • It is allowed to change the leading digit of a number into a zero, but this is never needed in the optimal solution.

Constraints

  • X will contain between 1 and 50 numbers, inclusive.
  • Each element of X will be between 0 and 10^6, inclusive.

Examples

  1. {5, 2, 8, 12}

    Returns: 3

    One optimal solution looks as follows: Ivan A. changes the 2 to a 1. Ivan A. changes the 8 to a 9. Ivan A. changes the last digit of the number 12 from 2 to 9. After these three steps he will have the sequence {5, 1, 9, 19}. The product of its elements is 5 * 1 * 9 * 19 = 855, so this sequence is pretty.

  2. {1555}

    Returns: 0

    The number already ends in a 5.

  3. {0, 10, 100, 1000, 10000}

    Returns: 5

    Clearly, Ivan A. must change the last digit in each of these numbers, otherwise the product would end in a 0. One optimal solution is to change this sequence into {7, 13, 105, 1005, 10003}.

  4. {1, 2, 2, 3, 3, 3, 4, 4, 4, 4}

    Returns: 6

  5. {7890, 4861, 65773, 3769, 4638, 46000, 548254, 36185, 115}

    Returns: 4

  6. {716421, 814337, 840046, 947217, 4399, 54055, 416453, 838171, 891638, 502326, 753001, 940168, 375733, 582140, 714961, 684089}

    Returns: 5

  7. {765505, 541952, 387331, 356497, 599617, 194677, 212171, 99765, 22610, 573583, 570253, 188534, 761346, 411811, 891664, 988309, 503157, 96406, 721167, 383129, 314922, 588047, 872141, 115089, 372349, 71725, 883941, 435449, 783884, 754491, 983634, 431801, 481141, 462761, 259321, 295232, 752453, 837867, 59569, 60961, 825525, 3665}

    Returns: 10

  8. {214708, 184435}

    Returns: 1

  9. {215119, 315697, 32000, 282774, 182497, 29613, 244937, 9269, 207793}

    Returns: 2

  10. {66271, 94809, 981938, 307719, 336451, 310646, 502201, 644241, 26363, 201737, 531455, 561537, 578339, 495126, 405609, 326561, 655579, 567569, 283151, 746851, 446161, 354137, 680437, 710256, 545783, 685859, 119721, 819343, 785417, 373901, 208693, 604076, 908267, 959446, 854459, 366276, 612927, 531001, 690501, 107077, 453600, 771073, 108689}

    Returns: 8

  11. {927041, 510817, 90609, 756947, 660481, 882011, 501477, 402471, 756369, 432401, 728657, 690293, 740491, 212799, 511697, 365371, 835381, 937501, 805641, 756929, 637443, 653483, 351851, 978221, 80001, 931113, 249003, 326489, 631987, 322873, 298011, 1753, 238001, 983233}

    Returns: 1

  12. {697973, 238649, 587221, 217107, 323041, 566101, 590801, 34189, 219291, 521809, 4077, 854849, 297993, 740161, 951251, 423041, 718351, 390577, 364109, 394377, 872331, 169653, 997377, 226389, 15097, 622191, 616601, 853967, 877901, 213041, 141197, 53489, 146737, 993759, 679421, 776131, 429591, 719909, 767501, 16461, 740563, 158113}

    Returns: 1

  13. {857081, 185901, 645331, 686673, 751581, 637207, 146097, 828929}

    Returns: 1

  14. {10391, 712057, 625841, 47657, 173543, 401561, 183171, 83411, 535321, 152849, 71429, 259577, 769101, 777751, 22193, 856741, 887989, 464781, 692691, 138021, 915489, 80153, 473107, 188803, 658043}

    Returns: 1

  15. {103509, 86481, 707649, 246337, 287633, 208277, 375849, 214281, 691553, 24813, 729671, 581701, 255811, 459071, 331257, 112773, 255729, 732349, 869781, 517881, 93661, 566269, 833623, 235341, 903819, 503057, 941447, 455797, 755363, 506809, 655651, 574251, 964041, 916107, 577461, 977249, 479297, 15181, 359707, 797831, 662963, 309501, 347121, 319289, 397921, 868257}

    Returns: 1

  16. {799784, 312958, 50206, 757758, 383444, 992212, 731666, 648328, 415766, 972268, 672626}

    Returns: 11

  17. {386106, 51538, 921974, 201126, 258106, 935706, 567234, 850746, 884196, 549276, 435324, 838834, 829446, 953518, 276082, 558444, 658282, 466644, 141874, 627886, 932164, 725098, 311696, 138496, 739234, 606582, 52246, 237634, 880706, 828826, 265886, 497782, 730832, 747666, 415902, 707758, 457172, 6664}

    Returns: 38

  18. {985426, 688836, 745024, 819686, 764914, 462914, 723904, 342238, 522832, 568362, 373878, 135298, 712844, 668076, 978742, 969008, 222606, 527586, 861574, 847738, 961018, 629854, 102956, 200698, 2236, 400598, 499482, 150496, 334616, 25386, 560226, 467412, 804094, 227346, 314424, 337636, 449628, 524866, 508176, 941588, 911254, 423958}

    Returns: 42

  19. {631026, 264076, 601512, 54886, 526716, 158802, 70632, 313108, 338362, 883054, 108404, 432758, 679826, 789542, 171428, 565036, 528076, 275132, 120082, 148318, 571222, 857756, 983632, 693162, 690912, 482664, 186726, 523642, 772272, 171592, 775654, 589416, 855336, 44526, 609006, 556796, 448562, 59264, 54242, 977086, 874612, 489242, 408798, 108708, 633796, 48168, 729974, 197646, 623382}

    Returns: 49

  20. {388788, 413456, 873268, 197714, 535666, 354926, 958546, 773926, 992324, 876076, 595846, 595888, 820222, 98126, 59596, 295688, 617498, 742034, 70822, 659464, 221738, 125452}

    Returns: 22

  21. {136745, 360225, 260265, 513145, 350575, 634605, 999455, 827215, 706325, 623275, 620005, 357245, 418755, 969725, 843765, 984265, 626305, 722175, 467705, 474945, 733035, 978855, 583945, 316865, 326325, 424945, 84815, 328545, 386705, 821825, 85375, 132315, 497345, 142785, 59545, 238315, 298095, 269725, 776305, 857145, 192755, 44805, 726245, 693855, 285025, 786215, 780265, 13065, 650305, 900555}

    Returns: 0

  22. {910485, 18945, 976625, 239585, 901445, 550175, 243655, 101585, 685675, 386345, 321025, 922525, 561735, 471345, 579435, 273705, 991845, 219715, 302765, 112165, 213405, 652915, 792265, 195135, 685425}

    Returns: 0

  23. {596475, 847305, 640745, 761105, 51665, 15625, 394645, 234525, 373745, 964365, 31165, 82145, 307085, 12805, 421215, 332725, 911435, 559455, 344625, 299185, 924975, 145305, 498505, 473845, 133035, 308135, 93945, 147615, 405225, 972585, 578565, 9505, 291825, 53605, 74945, 315505, 79465, 578995, 116205, 634535, 546375, 607505, 230505}

    Returns: 0

  24. {492305, 318535, 27345, 938425, 541465, 349825, 487985, 697845, 903415, 588585, 749565, 747975, 893385, 455535, 237705, 411465}

    Returns: 0

  25. {565025, 201565}

    Returns: 0

  26. {1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000}

    Returns: 50

  27. {276905, 1655, 21, 0, 0, 276905, 1655, 21, 0, 0, 276905, 1655, 21, 0, 0, 276905, 1655, 21, 0, 0, 276905, 1655, 21, 0, 0, 276905, 1655, 21, 0, 0, 276905, 1655, 21, 0, 0, 276905, 1655, 21, 0, 0, 276905, 1655, 21, 0, 0, 276905, 1655, 21, 0, 0}

    Returns: 20

  28. {95}

    Returns: 0

  29. {77777}

    Returns: 1

  30. {201520}

    Returns: 1

  31. {1,3,7,9,1111}

    Returns: 1

  32. {0}

    Returns: 1

  33. {1000000}

    Returns: 1

  34. {5,5,5,5,5,5,5}

    Returns: 0

  35. {1 }

    Returns: 1

  36. {1653 }

    Returns: 1

  37. {1, 1, 1 }

    Returns: 1

  38. {3, 3, 3 }

    Returns: 1

  39. {1, 3 }

    Returns: 1

  40. {15 }

    Returns: 0

  41. {5, 5, 3 }

    Returns: 0

  42. {3 }

    Returns: 1

  43. {1, 3, 7, 9 }

    Returns: 1

  44. {3, 7 }

    Returns: 1

  45. {5, 5 }

    Returns: 0

  46. {10 }

    Returns: 1

  47. {5 }

    Returns: 0

  48. {0, 10, 100, 1000, 10000 }

    Returns: 5

  49. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

    Returns: 1

  50. {65537, 65537, 65537, 65537 }

    Returns: 1

  51. {3, 5 }

    Returns: 0

  52. {3, 3, 3, 3, 3 }

    Returns: 1

  53. {5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5 }

    Returns: 0

  54. {0, 0, 0 }

    Returns: 3

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: