Statistics

Problem Statement for "Staircase"

Problem Statement

There is an ascending staircase where each step has a distinct absolute height above the floor given in inches. You must climb the staircase using a series of moves. On each move, you must do one of the following:
  • If the next step is 1 inch higher than your current step, you can go up to the next step.
  • If you are not on the first step, you can go down to the previous step.
  • If your K most recent moves have all been down, you can go up any number of steps, as long as you do not climb more than 2^K inches higher than your current step.

You are given a int[] stairs containing the heights of the steps from bottom to top. You are initially on the bottom step. Return the minimal number of moves necessary to reach the top step. Return -1 if it is impossible.

Definition

Class:
Staircase
Method:
minimalSteps
Parameters:
int[]
Returns:
int
Method signature:
int minimalSteps(int[] stairs)
(be sure your method is public)

Constraints

  • stairs will contain between 2 and 50 elements, inclusive.
  • The first element of stairs will be 0.
  • Elements of stairs will be in increasing order.
  • Each element of stairs will be between 0 and 109, inclusive.

Examples

  1. {0,1,2,3,6}

    Returns: 7

    Go three steps up, then three steps down, then go to the last step.

  2. {0,1,2,4,8}

    Returns: 9

    Up two steps, down two steps, up to the step of height 4, down three steps, then to the last step.

  3. {0,2,3,4,5,6,7,8}

    Returns: -1

    You can't do the first move.

  4. {0,1,2,3,5,10,100}

    Returns: -1

  5. {0,1,2,3,4,7,10,15,50,100,200,300,400,500,1000}

    Returns: 36

  6. {0, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131000, 260000, 512000, 1000000, 2000000, 4000000, 8000000, 16000000, 32000000, 64000000, 128000000, 256000000, 512000000, 900000000, 905000000, 910000000, 915000000, 920000000, 925000000, 930000000, 935000000, 940000000, 945000000, 950000000, 955000000, 960000000, 965000000, 970000000, 975000000, 980000000, 990000000, 1000000000}

    Returns: 495

  7. {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30, 31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49}

    Returns: 13

  8. {0,1,2,4,5,8,10,14,16,31,34,40,49,55,68,83,87,96}

    Returns: 19

  9. {0,1,2,3,4,6,9,17,21,33,42,44,45,48,52,58,63,64,65,67,72,73,77,79,82,85,93,94,106}

    Returns: 20

  10. {0,1,3,5,6,8,10,16,18,19,29,30,34,40,44,45,47,48,51,65,66,71,73,82,84,85,92,94,99,103,107}

    Returns: -1

  11. {0,1,2,4,6,7,9,11,19,50,55,60,61,68,69,75,93,96,107}

    Returns: 22

  12. {0,1,2,5,6,8,9,18,24,28,29,30,35,36,38,41,56,58,65,73,76,77,89,90,97,100,101,102}

    Returns: -1

  13. {0,1,3,6,7,9,10,34,86,99,100,104}

    Returns: -1

  14. {0,1,2,3,4,6,7,33,79}

    Returns: 21

  15. {0,1,3,4,5,6,8,12,26,27,31,32,34,36,43,53,54,62,64,65,69,75,85,92,106,109}

    Returns: -1

  16. {0,1,2,3,5,6,8,63,89,109}

    Returns: 22

  17. {0,1,3,6,7,8,9,17,29,30,32,35,39,42,48,55,63,65,66,67,68,76,81,84,89,94,99,100,105}

    Returns: -1

  18. {0,1,2,4,5,7,8,27,28,40,58,64,66,100,102}

    Returns: 23

  19. {0,1,3,4,8,9,10,25,80}

    Returns: -1

  20. {0,1,3,5,6,8,9,11,15,16,22,23,24,25,26,28,33,35,36,45,46,54,56,75,80,83,90,92,100,101,102,103}

    Returns: -1

  21. {0,1,2,3,4,9,10,15,51,65,72,77,91,105}

    Returns: 17

  22. {0,1,2,3,5,6,9,10,28,30,33,36,38,40,44,45,50,55,62,63,64,68,69,74,77,83,84,85,86,87,89,98,100,102,103}

    Returns: 19

  23. {0,1,2,5,6,8,9,14,16,17,21,32,39,43,47,54,55,58,60,62,67,70,83,85,92,93,95,96,101,104,105,108}

    Returns: -1

  24. {0,1,3,4,6,8,9,17,28,31,32,39,44,49,72,74,75,76,79,81,100,106,108}

    Returns: -1

  25. {0,1,3,4,6,8,9,10,11,16,22,31,32,44,47,48,49,51,52,56,59,60,62,67,72,81,88,89,91,94,95,99,102,106,107,109}

    Returns: -1

  26. {0,1,2,3,4,7,10,20,43,77,105}

    Returns: 21

  27. {0,1,3,4,6,8,9,16,18,21,23,24,29,30,32,36,43,50,54,58,59,60,67,75,79,80,82,91,93,99,100,107,109}

    Returns: -1

  28. {0,1,2,3,4,7,9,15,21,43,46}

    Returns: 15

  29. {0,1,4,5,6,7,9,19,24,102}

    Returns: -1

  30. {0,1,2,5,6,9,10,11,14,15,19,21,22,28,32,36,38,49,51,53,66,80,91,97,98,99,100,105}

    Returns: -1

  31. {0,1,3,4,8,9,10,13,15,17,30,31,38,39,41,42,43,44,53,57,58,67,72,74,85,91,94}

    Returns: -1

  32. {0,1,2,3,4,7,10,21,63,70,77,93,95,106}

    Returns: 21

  33. {0,1,2,3,4,6,7,13,44,61,66,68,69,81,91,95}

    Returns: 17

  34. {0,1,2,3,5,6,8,11,14,21,22,27,30,33,35,43,50,52,57,60,63,66,70,73,76,78,79,81,84,86,92,95,100}

    Returns: 19

  35. {0,1,2,4,5,6,10,16,27,44,45,57,73,90,99,102}

    Returns: 19

  36. {0,1,3,4,5,6,8,10,11,19,20,26,27,28,36,41,46,50,52,54,57,63,76,82,83,85,91,92,95,96,99,100,102,109}

    Returns: -1

  37. {0,1,3,5,6,7,9,10,18,26,38,69,75,80}

    Returns: -1

  38. {0,1,2,4,5,8,9,45,50,52,98,116,126,139,151,188,200,2848,4005,4570,6929,7646,9142,15206,15550,16090,19464,109824393}

    Returns: -1

  39. {0,1,2,5,6,7,10,12,30,46,51,93,101,158,160,184,205,253,2199,3399,4221,4684,4796,4934,7548,8481,19868,281109514,372814893,430906617,464622483,641627938,690003788,780602421,812600467}

    Returns: -1

  40. {0,1,2,4,7,9,10,11,55,75,80,118,128,133,142,150,154,3727,4672,5287,7352,8770,9963,10101,11800,14623,17303,134100608,154125347,205721221,208802943,263622409,468101588,556500028,646105049,696714015}

    Returns: -1

  41. {0,1,2,4,8,9,10,30,36,40,45,53,77,146,158,159,193,3559,4966,5829,7238,10053,11424,12457,15385,15948,20123,35331001,42414606,62429812,81105994,194625072,240106705,254709496,331632726,473529141,494414955,540921025,614131196,617124429,656416036,796323342,807517913,858309515,937430093}

    Returns: 129

  42. {0,1,2,3,6,7,9,21,25,35,40,47,51,100,141,165,196,1616,1834,1850,2433,5862,7462,10553,11093,13652,14208,107821318,112312317,222005402,356128489,365230674,367629643,402629200,415331361,421327109,425500148,494601282,526311903,545416303,663326303,685724050,690714902}

    Returns: -1

  43. {0,1,2,6,8,9,10,18,25,33,38,49,82,118,122,172,177,1158,4519,5404,6145,6634,7006,8366,9686,11959,18900,55330974,136617692,178528532}

    Returns: -1

  44. {0,1,2,3,4,5,8,86,88,91,103,109,139,163,175,194,205,5255,6173,6372,7714,9122,10129,10368,11391,11443,13808,98502144,291008146,579015469,644531577,651514629,674805651,991405874}

    Returns: -1

  45. {0,1,2,4,6,9,10,25,27,36,94,107,116,128,138,178,200,910,6285,7615,11985,12620,14686,15399,16013,18471,19399,26704693,31803580,130817604,133107267,267600406,318414507,436017827,715230271,776829022,807226431,838713444,941205000,988400337}

    Returns: 129

  46. {0,1,2,3,5,7,8,50,71,105,113,115,169,179,189,201,209,283,3852,4233,6453,7242,8881,8953,11620,12229,16187,224331063,581332718}

    Returns: -1

  47. {0,1,2,3,4,7,10,28,38,48,54,74,155,173,182,207,208,563,3892,4427,7804,9001,11397,11801,13690,14923,19971,180929151,301308055,339308738,527819882,674015022,742023445,772103565,860900495,929922363}

    Returns: -1

  48. {0,1,2,5,6,7,8,25,26,30,61,86,87,158,188,190,208,1862,3083,8462,11835,12379,17057,19102,19222,19620,19970,6510389,126611749,189213698,268528888,391731717,608002003,693225619,927325841}

    Returns: -1

  49. {0,1,2,4,5,6,9,60,93,95,96,112,138,165,191,197,200,1032,1089,3765,4072,4477,6624,6846,11062,11085,14628,77605821,125705045,267313336,273709310,292624773,385402520,492321265,513227251,633321001,647810883}

    Returns: -1

  50. {0,1,2,3,4,6,9,69,76,80,93,101,115,132,149,163,170,242,2245,3354,4829,5586,5652,8517,11887,12556,13588,46311833,94413793,109624314,126525776,304131376,400516469,421409722,531216626,546226260,562906738,631913053,775826919,862818717,984129007}

    Returns: -1

  51. {0,1,2,7,8,9,10,12,26,93,113,119,177,179,183,191,195,2066,3677,3887,5430,8510,8881,11445,13371,15767,17357,99716586,140500053,147722716,160204489,273822530,276106238,367424320,460828119,578813377,611304592,717120580,730932657,766902047,825805927,838826610,871726919,963029744}

    Returns: -1

  52. {0,1,2,4,6,7,9,34,37,45,53,94,103,116,129,198,201,740,2205,3782,8294,8827,9067,11346,12886,13424,16789}

    Returns: 45

  53. {0,1,2,4,5,8,9,14,34,37,78,96,108,112,127,165,166,1611,7289,7496,8610,9179,10958,10975,12689,13690,17332,12012529,43516693,105612826,151132125,175130397,183727296,194923112,290126758,397510670,458612021,507117916,671625328,767225836,827605553,893811544,908532652,975029001}

    Returns: 129

  54. {0,1,2,3,7,9,10,19,47,63,64,115,116,134,156,177,203,3261,4409,6406,9665,11236,12439,13847,15692,16699,18375,561725013,672515712,783920130,789421909,791506286,909009034}

    Returns: -1

  55. {0,1,2,6,8,9,10,12,36,49,72,89,105,116,124,160,196,3364,5876,6022,6238,7079,7557,12501,12770,16012,17976,431010144,656028180,819930643}

    Returns: -1

  56. {0,1,2,3,4,5,8,20,27,35,60,76,111,126,192,198,200,480,4793,5367,5393,5838,7238,8821,15095,16954,20182,18113817,18717839,38922632,59908252,67818613,121025429,147300617,212706753,215128318,226415966,469430833,490629554,514419861,688223865,741904345,896107813}

    Returns: 94

  57. {0,1,2,3,4,5,9,26,42,55,68,69,72,81,153,182,197,239,2215,3405,4641,11483,14176,16288,17883,18498,18716,52218345,77600786,91709387,97716085,238620373,348012073,501906030,576923675,744121735,838131785,999629146}

    Returns: 126

  58. {0, 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 45653 }

    Returns: 27

  59. {0, 1, 2, 4, 5, 6, 7, 64, 65, 66, 67, 1024, 1025, 1026, 1027, 16384, 16385, 16386, 16387, 262144, 262145, 262146, 262147, 4194304, 4194305, 4194306, 4194307, 67108864, 67108865, 67108866, 67108867, 67108868, 67108869, 67108870, 67108871, 67108872, 67108873, 67108874, 67108875, 67108876, 67108877, 67108878, 67108879, 67108880, 67108881, 67108882, 67108883, 67108884, 67108885, 67108886 }

    Returns: 136

  60. {0, 1, 2, 3, 4, 6, 7, 8, 16, 129, 512, 1024, 2048, 3510, 3511, 3512, 3513, 3514, 3515, 3516, 4517, 4518, 4529, 5024, 5048, 5050, 5096, 8192, 16384, 234534534, 467655536, 469131072, 888262144, 888262555, 888524288, 891048576, 962097152, 964194304, 968388608, 968777216, 973554432, 977108864, 977777424, 994217728, 998435456, 999870912, 999989898, 999999997, 999999999, 1000000000 }

    Returns: 168

  61. {0, 1, 2, 4, 8 }

    Returns: 9

  62. {0, 1, 2, 3, 8, 16, 24, 32, 45, 64, 71, 100, 125, 128, 150 }

    Returns: 34

  63. {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 29, 30, 1000000000 }

    Returns: -1

  64. {0, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 65537, 65538, 65540, 65541, 65550, 100000, 200000, 4000000, 4000001, 4000002, 5000000, 5000002, 5000004, 5000006, 5000008, 5000010, 10000000, 20000000, 40000000, 80000000, 100000000, 100000002, 100000004, 200000000, 200000010, 400000000, 800000000, 800000009, 900000000, 999999998, 1000000000 }

    Returns: 225

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: