Statistics

Problem Statement for "Gauss"

Problem Statement

Carl Friedrich Gauss (1777-1855) is considered to be one of the greatest mathematicians ever. There is a nice story about him being at elementary school: The teacher wanted to keep the class busy and assigned to them the task of adding all whole numbers from 1 to 100. While the other kids were just about to start their additions, Gauss already presented the result, 5050. He noticed that the numbers can be grouped into 50 pairs of value 101 (1+100, 2+99, ...), and from this he deduced that the sum of all natural numbers from 1 to n equals n(n+1)/2.

Now let's consider adding consecutive numbers not only starting at 1 but at any natural number. E.g. if you start at 13 and add three consecutive numbers, you get 13+14+15 = 42. Now can 42 also be achieved by adding two or more consecutive numbers starting at a different number? Yes, it can: 3+4+5+6+7+8+9 = 9+10+11+12 = 42.

Given a number target, return all intervals representing a sequence of two or more consecutive natural numbers (positive integers) that add up to target. The intervals have to be sorted by ascending lower interval limits. The interval representing the sequence a + (a+1) + ... + (b-1) + b is the String "[a, b]" (quotes for clarity; there is a single space between the comma and b).

Definition

Class:
Gauss
Method:
whichSums
Parameters:
String
Returns:
String[]
Method signature:
String[] whichSums(String target)
(be sure your method is public)

Notes

  • The value of target fits into a long.

Constraints

  • target represents a natural number between 1 and 10^11, inclusive, without leading zeros.

Examples

  1. "42"

    Returns: { "[3, 9]", "[9, 12]", "[13, 15]" }

    This is the example from the problem statement.

  2. "4"

    Returns: { }

    There are no 2 or more consecutive natural numbers that add up to 4.

  3. "17"

    Returns: { "[8, 9]" }

  4. "55"

    Returns: { "[1, 10]", "[9, 13]", "[27, 28]" }

  5. "1"

    Returns: { }

  6. "2"

    Returns: { }

  7. "3"

    Returns: { "[1, 2]" }

  8. "5"

    Returns: { "[2, 3]" }

  9. "6"

    Returns: { "[1, 3]" }

  10. "7"

    Returns: { "[3, 4]" }

  11. "8"

    Returns: { }

  12. "9"

    Returns: { "[2, 4]", "[4, 5]" }

  13. "10"

    Returns: { "[1, 4]" }

  14. "99999999997"

    Returns: { "[2941176454, 2941176487]", "[5882352933, 5882352949]", "[49999999998, 49999999999]" }

  15. "99999999998"

    Returns: { "[862068908, 862069023]", "[3448275848, 3448275876]", "[24999999998, 25000000001]" }

  16. "99999999999"

    Returns: { "[61779, 451460]", "[415819, 610659]", "[704912, 834805]", "[1507244, 1572190]", "[2287927, 2331224]", "[4608327, 4629975]", "[5555555547, 5555555564]", "[11111111107, 11111111115]", "[16666666664, 16666666669]", "[33333333332, 33333333334]", "[49999999999, 50000000000]" }

  17. "100000000000"

    Returns: { "[60688, 451312]", "[925363, 1027762]", "[1240938, 1319062]", "[4872573, 4893052]", "[6392188, 6407812]", "[24412015, 24416110]", "[31998438, 32001562]", "[159999688, 160000312]", "[799999938, 800000062]", "[3999999988, 4000000012]", "[19999999998, 20000000002]" }

  18. "65536"

    Returns: { }

  19. "4294967296"

    Returns: { }

  20. "68719476736"

    Returns: { }

  21. "39"

    Returns: { "[4, 9]", "[12, 14]", "[19, 20]" }

  22. "56"

    Returns: { "[5, 11]" }

  23. "656"

    Returns: { "[5, 36]" }

  24. "913"

    Returns: { "[31, 52]", "[78, 88]", "[456, 457]" }

  25. "8230"

    Returns: { "[402, 421]", "[1644, 1648]", "[2056, 2059]" }

  26. "3775"

    Returns: { "[51, 100]", "[139, 163]", "[373, 382]", "[753, 757]", "[1887, 1888]" }

  27. "52711"

    Returns: { "[26355, 26356]" }

  28. "47539"

    Returns: { "[37, 310]", "[279, 415]", "[23769, 23770]" }

  29. "730041"

    Returns: { "[9321, 9398]", "[18700, 18738]", "[28066, 28091]", "[56151, 56163]", "[121671, 121676]", "[243346, 243348]", "[365020, 365021]" }

  30. "890593"

    Returns: { "[40471, 40492]", "[80958, 80968]", "[445296, 445297]" }

  31. "3462649"

    Returns: { "[1267, 2920]", "[3774, 4600]", "[21837, 21994]", "[32614, 32719]", "[43792, 43870]", "[65307, 65359]", "[1731324, 1731325]" }

  32. "3453244"

    Returns: { "[2334, 3514]", "[4359, 5089]", "[9867, 10210]", "[25324, 25459]", "[80287, 80329]", "[203124, 203140]", "[431652, 431659]" }

  33. "10286461"

    Returns: { "[24165, 24586]", "[48646, 48856]", "[5143230, 5143231]" }

  34. "32142027"

    Returns: { "[277, 8022]", "[6363, 10235]", "[11158, 13739]", "[24252, 25542]", "[27178, 28335]", "[55224, 55802]", "[83077, 83462]", "[124453, 124710]", "[166443, 166635]", "[249099, 249227]", "[373702, 373787]", "[747468, 747510]", "[5357002, 5357007]", "[10714008, 10714010]", "[16071013, 16071014]" }

  35. "323600046"

    Returns: { "[349755, 350678]", "[1050496, 1050803]", "[1400751, 1400981]", "[2451450, 2451581]", "[3852340, 3852423]", "[4202560, 4202636]", "[7354525, 7354568]", "[9806046, 9806078]", "[11557131, 11557158]", "[15409516, 15409536]", "[26966665, 26966676]", "[29418181, 29418191]", "[46228575, 46228581]", "[80900010, 80900013]", "[107866681, 107866683]" }

  36. "679662059"

    Returns: { "[46727, 59520]", "[103049, 109445]", "[578342, 579515]", "[1157564, 1158150]", "[1877339, 1877700]", "[3754949, 3755129]", "[339831029, 339831030]" }

  37. "3674679277"

    Returns: { "[204349, 221602]", "[421638, 430264]", "[830299, 834712]", "[1663908, 1666114]", "[9519702, 9520087]", "[19039693, 19039885]", "[1837339638, 1837339639]" }

  38. "2766184524"

    Returns: { "[112339, 134730]", "[366872, 374335]", "[986877, 989675]", "[1110567, 1113054]", "[2964362, 2965294]", "[8894329, 8894639]", "[38419194, 38419265]", "[115257677, 115257700]", "[307353832, 307353840]", "[345773062, 345773069]", "[922061507, 922061509]" }

  39. "12624469209"

    Returns: { "[63759847, 63760044]", "[127519842, 127519940]", "[191279804, 191279869]", "[382559657, 382559689]", "[573839499, 573839520]", "[701359392, 701359409]", "[1147679014, 1147679024]", "[1402718797, 1402718805]", "[2104078199, 2104078204]", "[4208156402, 4208156404]", "[6312234604, 6312234605]" }

  40. "100000000000"

    Returns: { "[60688, 451312]", "[925363, 1027762]", "[1240938, 1319062]", "[4872573, 4893052]", "[6392188, 6407812]", "[24412015, 24416110]", "[31998438, 32001562]", "[159999688, 160000312]", "[799999938, 800000062]", "[3999999988, 4000000012]", "[19999999998, 20000000002]" }

  41. "9999999999"

    Returns: { "[20709, 142929]", "[49999, 149999]", "[50002, 150000]", "[81312, 163130]", "[116669, 183334]", "[156059, 210604]", "[159537, 213194]", "[283337, 316669]", "[353027, 380299]", "[359317, 386145]", "[438894, 461115]", "[540904, 559085]", "[550154, 568039]", "[894454, 905564]", "[1095444, 1104534]", "[1113722, 1122664]", "[1227772, 1235889]", "[1674309, 1680270]", "[2047582, 2052459]", "[2461632, 2465690]", "[3353089, 3356069]", "[3694139, 3696844]", "[4098822, 4101260]", "[6149249, 6150874]", "[7390307, 7391659]", "[11086024, 11086925]", "[12299717, 12300529]", "[13549767, 13550504]", "[18449914, 18450455]", "[22172724, 22173174]", "[27100087, 27100455]", "[36900234, 36900504]", "[40650284, 40650529]", "[50504952, 50505149]", "[81300752, 81300874]", "[101010052, 101010150]", "[121951179, 121951260]", "[151515119, 151515184]", "[243902419, 243902459]", "[303030287, 303030319]", "[454545444, 454545465]", "[555555547, 555555564]", "[909090904, 909090914]", "[1111111107, 1111111115]", "[1666666664, 1666666669]", "[3333333332, 3333333334]", "[4999999999, 5000000000]" }

  42. "99999999999"

    Returns: { "[61779, 451460]", "[415819, 610659]", "[704912, 834805]", "[1507244, 1572190]", "[2287927, 2331224]", "[4608327, 4629975]", "[5555555547, 5555555564]", "[11111111107, 11111111115]", "[16666666664, 16666666669]", "[33333333332, 33333333334]", "[49999999999, 50000000000]" }

  43. "123456789"

    Returns: { "[5117, 16525]", "[5999, 16819]", "[12429, 20034]", "[13507, 20720]", "[30562, 34364]", "[32424, 36030]", "[6858702, 6858719]", "[13717417, 13717425]", "[20576129, 20576134]", "[41152262, 41152264]", "[61728394, 61728395]" }

  44. "42"

    Returns: { "[3, 9]", "[9, 12]", "[13, 15]" }

  45. "92147483647"

    Returns: { "[2099638, 2143075]", "[4231854, 4253572]", "[78489604, 78490777]", "[156980088, 156980674]", "[1245236229, 1245236302]", "[2490472513, 2490472549]", "[46073741823, 46073741824]" }

  46. "50005000"

    Returns: { "[1, 10000]", "[918, 10042]", "[5643, 11482]", "[12888, 16312]", "[21717, 23908]", "[24003, 26002]", "[26488, 28312]", "[42229, 43396]", "[72658, 73342]", "[79696, 80320]", "[124813, 125212]", "[136818, 137182]", "[364932, 365068]", "[399978, 400102]", "[625023, 625102]", "[684964, 685036]", "[2000188, 2000212]", "[3125305, 3125320]", "[10000998, 10001002]" }

  47. "33333333333"

    Returns: { "[191673, 321566]", "[480766, 545712]", "[748210, 791507]", "[1528893, 1550541]", "[5555555553, 5555555558]", "[11111111110, 11111111112]", "[16666666666, 16666666667]" }

  48. "9999999967"

    Returns: { "[4999999983, 4999999984]" }

  49. "99999999977"

    Returns: { "[49999999988, 49999999989]" }

  50. "100000000000"

    Returns: { "[60688, 451312]", "[925363, 1027762]", "[1240938, 1319062]", "[4872573, 4893052]", "[6392188, 6407812]", "[24412015, 24416110]", "[31998438, 32001562]", "[159999688, 160000312]", "[799999938, 800000062]", "[3999999988, 4000000012]", "[19999999998, 20000000002]" }

  51. "9999999999"

    Returns: { "[20709, 142929]", "[49999, 149999]", "[50002, 150000]", "[81312, 163130]", "[116669, 183334]", "[156059, 210604]", "[159537, 213194]", "[283337, 316669]", "[353027, 380299]", "[359317, 386145]", "[438894, 461115]", "[540904, 559085]", "[550154, 568039]", "[894454, 905564]", "[1095444, 1104534]", "[1113722, 1122664]", "[1227772, 1235889]", "[1674309, 1680270]", "[2047582, 2052459]", "[2461632, 2465690]", "[3353089, 3356069]", "[3694139, 3696844]", "[4098822, 4101260]", "[6149249, 6150874]", "[7390307, 7391659]", "[11086024, 11086925]", "[12299717, 12300529]", "[13549767, 13550504]", "[18449914, 18450455]", "[22172724, 22173174]", "[27100087, 27100455]", "[36900234, 36900504]", "[40650284, 40650529]", "[50504952, 50505149]", "[81300752, 81300874]", "[101010052, 101010150]", "[121951179, 121951260]", "[151515119, 151515184]", "[243902419, 243902459]", "[303030287, 303030319]", "[454545444, 454545465]", "[555555547, 555555564]", "[909090904, 909090914]", "[1111111107, 1111111115]", "[1666666664, 1666666669]", "[3333333332, 3333333334]", "[4999999999, 5000000000]" }

  52. "99999999999"

    Returns: { "[61779, 451460]", "[415819, 610659]", "[704912, 834805]", "[1507244, 1572190]", "[2287927, 2331224]", "[4608327, 4629975]", "[5555555547, 5555555564]", "[11111111107, 11111111115]", "[16666666664, 16666666669]", "[33333333332, 33333333334]", "[49999999999, 50000000000]" }

  53. "123456789"

    Returns: { "[5117, 16525]", "[5999, 16819]", "[12429, 20034]", "[13507, 20720]", "[30562, 34364]", "[32424, 36030]", "[6858702, 6858719]", "[13717417, 13717425]", "[20576129, 20576134]", "[41152262, 41152264]", "[61728394, 61728395]" }

  54. "42"

    Returns: { "[3, 9]", "[9, 12]", "[13, 15]" }

  55. "92147483647"

    Returns: { "[2099638, 2143075]", "[4231854, 4253572]", "[78489604, 78490777]", "[156980088, 156980674]", "[1245236229, 1245236302]", "[2490472513, 2490472549]", "[46073741823, 46073741824]" }

  56. "50005000"

    Returns: { "[1, 10000]", "[918, 10042]", "[5643, 11482]", "[12888, 16312]", "[21717, 23908]", "[24003, 26002]", "[26488, 28312]", "[42229, 43396]", "[72658, 73342]", "[79696, 80320]", "[124813, 125212]", "[136818, 137182]", "[364932, 365068]", "[399978, 400102]", "[625023, 625102]", "[684964, 685036]", "[2000188, 2000212]", "[3125305, 3125320]", "[10000998, 10001002]" }

  57. "33333333333"

    Returns: { "[191673, 321566]", "[480766, 545712]", "[748210, 791507]", "[1528893, 1550541]", "[5555555553, 5555555558]", "[11111111110, 11111111112]", "[16666666666, 16666666667]" }

  58. "9999999967"

    Returns: { "[4999999983, 4999999984]" }

  59. "99999999977"

    Returns: { "[49999999988, 49999999989]" }

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: