Statistics

Problem Statement for "DesignCalendar"

Problem Statement

An alien civilization has advanced to the point where it needs to start keeping track of time. Its leaders have therefore decided to design a calendar. Like many Earthly calendars, this calendar is going to be based on the motion of celestial bodies: in particular the calendar must include period of rotation of their planet (a day) and the period of orbit of the planet around the sun (a real year). Unfortunately, just as is the case on Earth, a real year is not necessarily a convenient integer number of days. Their solution to this problem is to define a calendar year, which is an integer number of days long, and periodically insert an extra day into some calendar years (leap years) in order to correct the discrepancy and resychronize the start of the calendar year with the start of the real year.

The formal requirements for the calendar are as follows:

  • A normal calendar year is a length of time that is some integer number N days long.
  • A leap calendar year is exactly one day longer than a normal calendar year (N+1 days long).
  • Each calendar year is either a normal year or a leap year.
  • The calendar must have some positive integer period P, such that every P whole consecutive calendar years sum to exactly the same length of time as P real years.

The leaders wish to design the calendar to make the period P as short as possible. A day is dayLength time units long and a real year is yearLength time units long. Return the smallest achievable positive integer value of P.

Definition

Class:
DesignCalendar
Method:
shortestPeriod
Parameters:
int, int
Returns:
int
Method signature:
int shortestPeriod(int dayLength, int yearLength)
(be sure your method is public)

Constraints

  • yearLength will be between 1 and 1000000000 (10^9), inclusive.
  • dayLength will be between 1 and yearLength, inclusive.

Examples

  1. 4

    1461

    Returns: 4

    These are the values for the Earth to the nearest quarter day. A days here is 4 quarter days long and a year is 365 * 4 + 1 = 1461 quarter days long. A single leap year every 4 years keeps the calendar synchronized.

  2. 86400

    31558150

    Returns: 1728

    These are the values for the Earth to the nearest second. A calendar with a period of 1728 years would be aligned to the start of the solar year to within a second after the first period.

  3. 98

    100

    Returns: 49

  4. 1000

    50000100

    Returns: 10

  5. 5673

    28565335

    Returns: 5673

  6. 5555

    846555

    Returns: 1111

  7. 1

    1

    Returns: 1

  8. 10

    100

    Returns: 1

  9. 10000000

    1000000000

    Returns: 1

  10. 999999999

    1000000000

    Returns: 999999999

  11. 500000001

    1000000000

    Returns: 500000001

  12. 500000003

    1000000000

    Returns: 500000003

  13. 82

    15204

    Returns: 41

  14. 13082

    31861

    Returns: 62

  15. 403799319

    509735122

    Returns: 403799319

  16. 135489006

    351810238

    Returns: 67744503

  17. 39178655

    337430093

    Returns: 39178655

  18. 1110459

    3823580

    Returns: 1110459

  19. 677953537

    733498447

    Returns: 677953537

  20. 475102229

    567113209

    Returns: 475102229

  21. 146771956

    537844882

    Returns: 73385978

  22. 137846540

    713943589

    Returns: 137846540

  23. 159296339

    271777533

    Returns: 159296339

  24. 133447241

    270554780

    Returns: 133447241

  25. 203717349

    229767078

    Returns: 67905783

  26. 175254045

    623156945

    Returns: 35050809

  27. 81508907

    315757783

    Returns: 81508907

  28. 14822170

    58529122

    Returns: 7411085

  29. 349731837

    550845702

    Returns: 38859093

  30. 62048314

    143678497

    Returns: 62048314

  31. 57870343

    104217818

    Returns: 57870343

  32. 273493092

    998092297

    Returns: 273493092

  33. 629149

    216683818

    Returns: 629149

  34. 44247326

    57323853

    Returns: 44247326

  35. 149798163

    278890753

    Returns: 149798163

  36. 123733566

    129676107

    Returns: 3749502

  37. 18835015

    23388563

    Returns: 400745

  38. 18238173

    501964947

    Returns: 6079391

  39. 634333141

    871247433

    Returns: 634333141

  40. 163227620

    601223908

    Returns: 40806905

  41. 87096831

    466136762

    Returns: 87096831

  42. 23704993

    32218928

    Returns: 23704993

  43. 171036604

    363119789

    Returns: 171036604

  44. 125411702

    360268690

    Returns: 62705851

  45. 14338178

    462655516

    Returns: 7169089

  46. 39599910

    48518492

    Returns: 19799955

  47. 15574365

    115410731

    Returns: 15574365

  48. 751016177

    803999503

    Returns: 751016177

  49. 44469464

    45529651

    Returns: 44469464

  50. 356251142

    636214872

    Returns: 178125571

  51. 201565838

    207950781

    Returns: 201565838

  52. 26870741

    471339543

    Returns: 26870741

  53. 4367239

    496206463

    Returns: 4367239

  54. 139952609

    700270685

    Returns: 139952609

  55. 41332253

    647048032

    Returns: 41332253

  56. 340063063

    545561704

    Returns: 340063063

  57. 115375820

    847906168

    Returns: 28843955

  58. 6490633

    246420647

    Returns: 6490633

  59. 228796752

    426078735

    Returns: 1622672

  60. 130012489

    693817532

    Returns: 130012489

  61. 474449252

    503597725

    Returns: 474449252

  62. 153493214

    515635060

    Returns: 76746607

  63. 111758095

    880946888

    Returns: 111758095

  64. 103068480

    274916560

    Returns: 1288356

  65. 36901786

    513050110

    Returns: 18450893

  66. 6544111

    92024119

    Returns: 6544111

  67. 200016

    3851356

    Returns: 50004

  68. 60488587

    944110755

    Returns: 60488587

  69. 299088

    58184703

    Returns: 33232

  70. 26304256

    351887942

    Returns: 13152128

  71. 6925531

    339292005

    Returns: 6925531

  72. 3251535

    127489168

    Returns: 3251535

  73. 2079018

    464392819

    Returns: 2079018

  74. 20840778

    211310177

    Returns: 20840778

  75. 1

    5

    Returns: 1

  76. 982451653

    1000000000

    Returns: 982451653

  77. 416136506

    633781683

    Returns: 416136506

  78. 999999997

    999999999

    Returns: 999999997

  79. 10000001

    99999999

    Returns: 909091

  80. 3021375

    3021377

    Returns: 3021375

  81. 4

    8

    Returns: 1

  82. 10

    20

    Returns: 1

  83. 90000011

    900000013

    Returns: 90000011

  84. 600000001

    700000001

    Returns: 600000001

  85. 531807762

    778010983

    Returns: 531807762

  86. 99999997

    1000000000

    Returns: 99999997

  87. 10

    10

    Returns: 1

  88. 549876685

    846555154

    Returns: 549876685

  89. 423432

    834241298

    Returns: 211716

  90. 999917171

    999971717

    Returns: 999917171

  91. 500000000

    999999999

    Returns: 500000000

  92. 999999929

    999999937

    Returns: 999999929

  93. 999999997

    999999998

    Returns: 999999997

  94. 33

    99

    Returns: 1

  95. 2

    4

    Returns: 1

  96. 10

    1000

    Returns: 1

  97. 1

    1000000000

    Returns: 1

  98. 5

    10

    Returns: 1

  99. 982451653

    982451654

    Returns: 982451653

  100. 2

    5

    Returns: 2

  101. 3

    9

    Returns: 1

  102. 1

    2

    Returns: 1

  103. 999999997

    1000000000

    Returns: 999999997

  104. 99999998

    99999999

    Returns: 99999998

  105. 4

    256

    Returns: 1

  106. 999999001

    999999059

    Returns: 999999001

  107. 900000001

    999999999

    Returns: 900000001

  108. 1000000000

    1000000000

    Returns: 1

  109. 4234329

    834241298

    Returns: 384939

  110. 999991

    1000000000

    Returns: 999991

  111. 100000000

    199999999

    Returns: 100000000

  112. 2

    6

    Returns: 1

  113. 999999677

    1000000000

    Returns: 999999677

  114. 4

    4

    Returns: 1

  115. 999999998

    999999999

    Returns: 999999998

  116. 3

    3

    Returns: 1

  117. 1

    100

    Returns: 1

  118. 715827883

    999999937

    Returns: 715827883

  119. 925234243

    1000000000

    Returns: 925234243

  120. 999999929

    999999930

    Returns: 999999929

  121. 100

    100

    Returns: 1

  122. 999999929

    999999932

    Returns: 999999929

  123. 999999883

    999999937

    Returns: 999999883

  124. 2

    2

    Returns: 1

  125. 123456789

    999999999

    Returns: 13717421

  126. 999999986

    1000000000

    Returns: 499999993

  127. 1000

    100000000

    Returns: 1

  128. 100

    200

    Returns: 1

  129. 209161009

    209231866

    Returns: 209161009

  130. 800100001

    1000000000

    Returns: 800100001

  131. 1000

    1000

    Returns: 1

  132. 4

    1460

    Returns: 1

  133. 4

    7

    Returns: 4

  134. 10000000

    19999999

    Returns: 10000000

  135. 50

    100

    Returns: 1

  136. 1061

    1061

    Returns: 1

  137. 3215231

    302137743

    Returns: 3215231

  138. 961274177

    1000000000

    Returns: 961274177

  139. 823456787

    1000000000

    Returns: 823456787

  140. 5

    5

    Returns: 1

  141. 499999999

    500000000

    Returns: 499999999

  142. 737312243

    1000000000

    Returns: 737312243

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: