Statistics

Problem Statement for "MissingLCM"

Problem Statement

The least common multiple (denoted "lcm") of a non-empty sequence of positive integers is the smallest positive integer that is divisible by each of them. For example, lcm(2)=2, lcm(4,6)=12, and lcm(1,2,3,4,5)=60.

Alice had a positive integer N. Then she chose some positive integer M that was strictly greater than N. Afterwards, she computed two values: the value A = lcm(N+1, N+2, ..., M) and the value B = lcm(1, 2, ..., M). She was surprised when she saw that A = B.

You are given the int N. Find and return the smallest M Alice could have chosen. (Such an M will always exist.)

Definition

Class:
MissingLCM
Method:
getMin
Parameters:
int
Returns:
int
Method signature:
int getMin(int N)
(be sure your method is public)

Constraints

  • N will be between 1 and 1,000,000, inclusive.

Examples

  1. 1

    Returns: 2

    Alice needs to choose an M > 1 such that lcm(2,...,M) = lcm(1,...,M). We can see M=2 is the minimum value that works, since lcm(1,2) = lcm(2) = 2.

  2. 2

    Returns: 4

  3. 3

    Returns: 6

    We have lcm(4,5,6) = lcm(1,2,3,4,5,6) = 60.

  4. 4

    Returns: 8

  5. 5

    Returns: 10

  6. 42

    Returns: 82

    Oh... that doesn't fit the pattern.

  7. 999999

    Returns: 1999966

  8. 1000000

    Returns: 1999966

  9. 10

    Returns: 18

  10. 100

    Returns: 194

  11. 1000

    Returns: 1994

  12. 10000

    Returns: 19946

  13. 100000

    Returns: 199982

  14. 279841

    Returns: 559682

  15. 531445

    Returns: 1062882

  16. 161052

    Returns: 322102

  17. 161055

    Returns: 322106

  18. 994012

    Returns: 1988018

  19. 386181

    Returns: 772346

  20. 559460

    Returns: 1118918

  21. 823661

    Returns: 1647302

  22. 627547

    Returns: 1255094

  23. 904541

    Returns: 1809062

  24. 856252

    Returns: 1712498

  25. 509533

    Returns: 1019042

  26. 223449

    Returns: 446882

  27. 832585

    Returns: 1665166

  28. 986047

    Returns: 1972094

  29. 37834

    Returns: 75662

  30. 33298

    Returns: 66578

  31. 79002

    Returns: 157978

  32. 27258

    Returns: 54506

  33. 44618

    Returns: 89234

  34. 6423

    Returns: 12842

  35. 4836

    Returns: 9662

  36. 4058

    Returns: 8114

  37. 8566

    Returns: 17126

  38. 6951

    Returns: 13898

  39. 408

    Returns: 802

  40. 395

    Returns: 778

  41. 377

    Returns: 746

  42. 573

    Returns: 1142

  43. 54

    Returns: 106

  44. 90

    Returns: 178

  45. 33

    Returns: 64

  46. 30

    Returns: 58

  47. 23

    Returns: 46

  48. 531441

    Returns: 1062882

  49. 8

    Returns: 16

  50. 81

    Returns: 162

  51. 9

    Returns: 18

  52. 28

    Returns: 54

  53. 16

    Returns: 32

  54. 27

    Returns: 54

  55. 262144

    Returns: 524288

  56. 103823

    Returns: 207646

  57. 1350

    Returns: 2662

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: