Statistics

Problem Statement for "RestoreExpression"

Problem Statement

Consider a simple arithmetic expression, A+B=C, where A, B, C are nonnegative integers without leading zeroes. Unfortunately, some digits are unknown and are replaced by the symbol '?'. You task is to restore the expression.

You are given a String expression. The resulting String must contain the same expression, but with the symbols '?' replaced by digits so that the expression is correct. Numbers in the resulting String must not have leading zeroes.

For example, given the string "5+?=?4" you should return "5+9=14".

If multiple solutions exist, return the one with the maximum possible C. If more than one such solution exists, return the one among them that maximizes the value of A. If there is no solution, return "no solution" (quotes for clarity).

Definition

Class:
RestoreExpression
Method:
restore
Parameters:
String
Returns:
String
Method signature:
String restore(String expression)
(be sure your method is public)

Constraints

  • expression will contain between 5 and 50 characters, inclusive.
  • expression will be formatted as "A+B=C" (quotes for clarity), where A, B and C are nonnegative integers (without leading zeroes) with some digits possibly replaced by '?'.

Examples

  1. "5+?=?4"

    Returns: "5+9=14"

    This is the example from the problem statement. 5+9=14 is the only solution.

  2. "?+?=4"

    Returns: "4+0=4"

    There are five possible solutions, all of which have the same value of C. 4+0=4 maximizes A.

  3. "?+?=?"

    Returns: "9+0=9"

  4. "?2+?2=4"

    Returns: "no solution"

  5. "??+1=1?"

    Returns: "18+1=19"

  6. "??????????+??????????=??????????"

    Returns: "8999999999+1000000000=9999999999"

  7. "123456789+987654321=1111111110"

    Returns: "123456789+987654321=1111111110"

  8. "?2?4?6?8?+9?7?5?2?=1?1?1?1?1?"

    Returns: "928486889+90705029=1019191918"

  9. "??+??????????????????????=??????????????????????"

    Returns: "99+9999999999999999999900=9999999999999999999999"

  10. "?+??????????????????????=???????????????????????"

    Returns: "9+9999999999999999999999=10000000000000000000008"

  11. "????????????????+????????????????=????????????????"

    Returns: "8999999999999999+1000000000000000=9999999999999999"

  12. "??1?2???3??4????+?6??7?8??9???4??=??2??3??4??5?6??"

    Returns: "8319231930949299+1610708019010400=9929939949959699"

  13. "??1?2???3??4????+?6??7?8??99??4??=??2??3??4??5?6?9"

    Returns: "8319231930049299+1610708019910400=9929939949959699"

  14. "3?+??=50"

    Returns: "39+11=50"

  15. "?50+?50=100"

    Returns: "no solution"

  16. "9?9+??=999"

    Returns: "989+10=999"

  17. "???+?=???0"

    Returns: "999+1=1000"

  18. "1234567891234567+1234567891234567=2469135782469134"

    Returns: "1234567891234567+1234567891234567=2469135782469134"

  19. "?2345??891234567+1?34??6891234567=2469???78246???4"

    Returns: "1234599891234567+1234996891234567=2469596782469134"

  20. "?2345??891???567+1?34??6891?3?5?7=2469???78246???4"

    Returns: "1234599891438567+1234996891030597=2469596782469164"

  21. "?2345??891???55+??34??6891?3?5?=?2469???78246???"

    Returns: "923459989143855+323499689103059=1246959678246914"

  22. "?2345??891???55+1?34??6891?3?5?=?2469???78246???"

    Returns: "no solution"

  23. "?2345??891???55+2?34??6891?3?5?=?2469???78246???"

    Returns: "no solution"

  24. "?2345??891???55+4?34??6891?3?5?=?2469???78246???"

    Returns: "823459989143855+423499689103059=1246959678246914"

  25. "?2345??891???55+??34??6891?3?5?=12469???78246???"

    Returns: "923459989143855+323499689103059=1246959678246914"

  26. "?2345??891???55+4?34??6891?3?5?=?2469???78246??1"

    Returns: "823459989143855+423499689103056=1246959678246911"

  27. "?2345??891???55+4?34??6891?3?5?=?2469???78246??2"

    Returns: "823459989143855+423499689103057=1246959678246912"

  28. "?2345??891???55+4?34??6891?3?5?=?2469???78246??3"

    Returns: "823459989143855+423499689103058=1246959678246913"

  29. "?2345??891???55+4134??6891?3?5?=?2469???78246??3"

    Returns: "no solution"

  30. "581+4??=100?"

    Returns: "581+428=1009"

  31. "5???????????????+????????????????=7???????????????"

    Returns: "5999999999999999+2000000000000000=7999999999999999"

  32. "30+??=50"

    Returns: "30+20=50"

  33. "9+?=?1"

    Returns: "9+2=11"

  34. "??+44=96"

    Returns: "52+44=96"

  35. "53+44=96"

    Returns: "no solution"

  36. "??+??=96"

    Returns: "86+10=96"

  37. "8??+??=9?6"

    Returns: "899+97=996"

  38. "9?+1??=106"

    Returns: "no solution"

  39. "??+?=18"

    Returns: "18+0=18"

  40. "?+??=18"

    Returns: "8+10=18"

  41. "15+??=15"

    Returns: "no solution"

  42. "??+15=15"

    Returns: "no solution"

  43. "1+2=4"

    Returns: "no solution"

  44. "15+15=??"

    Returns: "15+15=30"

  45. "1+2=?4"

    Returns: "no solution"

  46. "1?+2?=4?"

    Returns: "19+29=48"

  47. "?+???????????????????????=????????????????????????"

    Returns: "9+99999999999999999999999=100000000000000000000008"

  48. "???????????????????????+?=????????????????????????"

    Returns: "99999999999999999999999+9=100000000000000000000008"

  49. "??+??????????????????????=????????????????????????"

    Returns: "no solution"

  50. "?????????????????????+???=????????????????????????"

    Returns: "no solution"

  51. "8+8=6"

    Returns: "no solution"

  52. "8+8=16"

    Returns: "8+8=16"

  53. "1+9999999999999999999999?=???????????????????????"

    Returns: "1+99999999999999999999998=99999999999999999999999"

  54. "1+9999999999999999999999?=????????????????????????"

    Returns: "1+99999999999999999999999=100000000000000000000000"

  55. "9999999999999999999999?+1=???????????????????????"

    Returns: "99999999999999999999998+1=99999999999999999999999"

  56. "9999999999999999999999?+1=????????????????????????"

    Returns: "99999999999999999999999+1=100000000000000000000000"

  57. "?+?=19"

    Returns: "no solution"

  58. "?+?=0"

    Returns: "0+0=0"

  59. "1+99999999999999999999999=???????????????????????"

    Returns: "no solution"

  60. "99999999999999999999999+1=???????????????????????"

    Returns: "no solution"

  61. "?????????6????????????+?=?????????7????????????"

    Returns: "9999999996999999999999+9=9999999997000000000008"

  62. "???????????????9+???????????????9=???????????????9"

    Returns: "no solution"

  63. "?+?=4"

    Returns: "4+0=4"

  64. "1?2?3?4?5?6?7?8+???????????????=2?3?4?5?6?7?8?9"

    Returns: "192939495969798+101010101010101=293949596979899"

  65. "??????????????????????+??=????10????5???????????"

    Returns: "9999109999599999999989+10=9999109999599999999999"

  66. "?0?7??????3?0???+?07???3???0????=??0?10????5?????"

    Returns: "9097999699390999+807110300209000=9905109999599999"

  67. "?????2+?????2=4"

    Returns: "no solution"

  68. "???????????4+???????????7=???????????2"

    Returns: "no solution"

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: