Statistics

Problem Statement for "BinarySum"

Problem Statement

You are given three integers: a, b and c. Convert each of them into their binary representations with no leading zeroes. Let x be the number of binary digits in the longest of the three. Add leading zeroes to the others until all of them have exactly x digits.

Transform a, b and c into a', b' and c', such that a'+b'=c', by optionally reordering the digits within each number. Leading zeroes are allowed. If there are several ways to do this, use the one that minimizes c'.

For example, let a = 7, b = 6 and c = 9. In binary notation, a = 111, b = 110 and c = 1001. We add leading zeroes to a and b so that all of them have exactly four digits: a = 0111, b = 0110, c = 1001. Now, if we reorder the digits within each number to get a' = 0111, b' = 0011 and c' = 1010, we satisfy a' + b' = c' (7 + 3 = 10). There is another way to do this as well (7 + 5 = 12), but this is the way that minimizes c'.

You are given ints a, b and c. Return the minimal possible value of c'. If there is no solution, return -1.

Definition

Class:
BinarySum
Method:
rearrange
Parameters:
int, int, int
Returns:
int
Method signature:
int rearrange(int a, int b, int c)
(be sure your method is public)

Constraints

  • a, b and c will each be between 1 and 2^30, inclusive.

Examples

  1. 7

    6

    9

    Returns: 10

    The example from the problem statement.

  2. 1

    1

    2

    Returns: 2

  3. 1

    1

    4

    Returns: 2

    Leading zeroes are allowed.

  4. 3

    3

    9

    Returns: 6

  5. 334308079

    476771809

    343926580

    Returns: 524285

  6. 18172390

    41867037

    999427053

    Returns: 262111

  7. 683530770

    137378236

    675703779

    Returns: 65527

  8. 170016738

    902057161

    265484073

    Returns: 524031

  9. 500520964

    537509546

    592180714

    Returns: 523263

  10. 430086116

    887170523

    6281675

    Returns: 131069

  11. 787785777

    423463137

    310328573

    Returns: 2095103

  12. 290851885

    51934273

    891027928

    Returns: 8187

  13. 511949054

    442760166

    901643062

    Returns: 4194271

  14. 643436451

    83195948

    955079174

    Returns: 65533

  15. 168908749

    138562579

    723957692

    Returns: 516095

  16. 45179388

    677490732

    747468457

    Returns: 130943

  17. 96993927

    335745781

    899018129

    Returns: 258047

  18. 396453200

    169516336

    693155749

    Returns: 65503

  19. 573964371

    55031861

    511623689

    Returns: 65471

  20. 272264949

    344362611

    131920742

    Returns: 524223

  21. 577323191

    840480064

    693103993

    Returns: 1032191

  22. 594133114

    139016882

    762288915

    Returns: 523263

  23. 552100167

    279010029

    332440803

    Returns: 32763

  24. 118864300

    485000945

    597934037

    Returns: 1048319

  25. 707809105

    116402606

    763510994

    Returns: 67582

  26. 204650420

    636233541

    457934933

    Returns: 81918

  27. 431782887

    361323438

    750230794

    Returns: 1114110

  28. 56395884

    170314172

    506151426

    Returns: 34814

  29. 166057945

    469458319

    482778608

    Returns: 8454142

  30. 348338570

    885811186

    425280085

    Returns: 139262

  31. 275146495

    189160767

    645183519

    Returns: 327678

  32. 463065908

    779453393

    238505068

    Returns: 163838

  33. 74798816

    368808961

    93985640

    Returns: 24574

  34. 830661721

    666606594

    45115527

    Returns: 133118

  35. 759631323

    464930002

    362013352

    Returns: 278526

  36. 663921340

    505544263

    379966729

    Returns: 278526

  37. 908828453

    67074162

    359668590

    Returns: 1081342

  38. 284597365

    450661594

    285622582

    Returns: 4195326

  39. 407680818

    436137858

    242487569

    Returns: 4196350

  40. 850183862

    791364174

    78578812

    Returns: 270334

  41. 463369521

    419558259

    570912045

    Returns: 278526

  42. 163816063

    4895939

    457717825

    Returns: 67582

  43. 595601367

    255897532

    206128265

    Returns: 1049598

  44. 842474456

    122256606

    815696142

    Returns: 532478

  45. 775842374

    663855624

    674910300

    Returns: 69629

  46. 32613170

    799426463

    777345314

    Returns: 540669

  47. 753954787

    148166354

    226817449

    Returns: 294909

  48. 433432006

    642079787

    208602097

    Returns: 98301

  49. 820809451

    471294884

    599399146

    Returns: 196603

  50. 161236053

    334227003

    856858256

    Returns: 532477

  51. 493105378

    259764372

    348681398

    Returns: 81917

  52. 103853069

    558377207

    696693002

    Returns: 12285

  53. 493397717

    68573601

    348623590

    Returns: 98287

  54. 926794269

    378544735

    332477417

    Returns: 196599

  55. 609412229

    536362060

    549268260

    Returns: 139261

  56. 252673000

    47224135

    347942665

    Returns: 294903

  57. 805905811

    362697427

    74437218

    Returns: 81911

  58. 833460691

    7701620

    24520642

    Returns: 139259

  59. 808082923

    402025818

    493867209

    Returns: 655357

  60. 828560563

    428529673

    714586624

    Returns: 40957

  61. 46325286

    936557597

    114482845

    Returns: 393199

  62. 217340200

    511007723

    797664162

    Returns: 1114103

  63. 92639369

    861761590

    588890197

    Returns: 69627

  64. 24291185

    652719266

    898266435

    Returns: 98301

  65. 1073741824

    1073741824

    1073741824

    Returns: 2

  66. 1073741824

    1073741824

    3

    Returns: 3

  67. 1073741824

    1

    3

    Returns: 3

  68. 1073741824

    2

    6

    Returns: 3

  69. 1

    1

    1

    Returns: -1

  70. 641466323

    542463831

    655632

    Returns: -1

  71. 199520125

    242107297

    33029

    Returns: -1

  72. 250551832

    115435381

    130

    Returns: -1

  73. 729149929

    231110416

    16896

    Returns: -1

  74. 310328573

    313118170

    32

    Returns: -1

  75. 485000945

    597934037

    49192

    Returns: -1

  76. 32517565

    204650420

    4096

    Returns: -1

  77. 884897929

    736457454

    4486

    Returns: -1

  78. 166057945

    469458319

    262147

    Returns: -1

  79. 275146495

    189160767

    262145

    Returns: -1

  80. 958706524

    357678745

    1

    Returns: -1

  81. 531236552

    352277811

    128

    Returns: -1

  82. 11621717

    225784555

    4096

    Returns: -1

  83. 651619703

    850183862

    264209

    Returns: -1

  84. 799426463

    777345314

    65538

    Returns: -1

  85. 599399146

    473927417

    137352

    Returns: -1

  86. 962818762

    701444969

    16576

    Returns: -1

  87. 408628931

    493397717

    512

    Returns: -1

  88. 595064042

    239089639

    524288

    Returns: -1

  89. 932393998

    736574814

    2114

    Returns: -1

  90. 268435456

    268435455

    536870912

    Returns: 268435456

  91. 268435456

    268435455

    536870911

    Returns: 536870911

  92. 1073741824

    1073741823

    1073741823

    Returns: 1610612735

  93. 978211420

    794211960

    739208423

    Returns: 393211

  94. 987654321

    987654321

    987654321

    Returns: 262142

  95. 121

    211

    1073741824

    Returns: 512

  96. 23435535

    2343434

    1073741822

    Returns: -1

  97. 135321

    315236

    31

    Returns: 2078

  98. 16383111

    16383

    32767

    Returns: 98301

  99. 14650420

    23455697

    20123343

    Returns: 49149

  100. 32517565

    204650420

    1073741824

    Returns: 536870912

  101. 65536

    65536

    1

    Returns: 2

  102. 16383

    131071

    67125247

    Returns: 163837

  103. 1073741823

    1073741823

    1073741823

    Returns: -1

  104. 1020414119

    691966380

    137768724

    Returns: 266238

  105. 1073741824

    1073741824

    1

    Returns: 2

  106. 268419072

    16383

    268435455

    Returns: 268435455

  107. 1073741823

    1

    1073741824

    Returns: 1073741824

  108. 2

    2

    1

    Returns: 2

  109. 32132154

    123564655

    981234564

    Returns: 327671

  110. 31

    15

    112

    Returns: 70

  111. 789789789

    789789789

    678678678

    Returns: 1064958

  112. 1073741824

    1073741823

    1

    Returns: 1073741824

  113. 234234

    2342343

    534534545

    Returns: 261631

  114. 1048575

    204650420

    1048575

    Returns: 2097119

  115. 1073709056

    1073709056

    1073741822

    Returns: 805306367

  116. 1073709056

    32767

    1073741823

    Returns: 1073741823

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: