Statistics

Problem Statement for "ProductsMatrix"

Problem Statement

Consider a square n x n matrix A. The cell Ai,j is equal to the product i * j (i, j are 1-based). Let's create a one-dimensional array which contains all the elements of the matrix A. The length of this array will be equal to n2. Sort this array and return the element which will be in the k-th position (k is a 1-based index).

Definition

Class:
ProductsMatrix
Method:
nthElement
Parameters:
int, int
Returns:
long
Method signature:
long nthElement(int n, int k)
(be sure your method is public)

Constraints

  • n will be between 1 and 10^5, inclusive.
  • k will be between 1 and min(10^9, n^2), inclusive.

Examples

  1. 3

    7

    Returns: 6

    The matrix will be: 1 2 3 2 4 6 3 6 9 The array after sorting will be: {1, 2, 2, 3, 3, 4, 6, 6, 9}.

  2. 2

    4

    Returns: 4

    k is 1-based.

  3. 3

    8

    Returns: 6

  4. 1

    1

    Returns: 1

  5. 4

    4

    Returns: 3

  6. 1

    1

    Returns: 1

  7. 2

    1

    Returns: 1

  8. 2

    2

    Returns: 2

  9. 2

    3

    Returns: 2

  10. 2

    4

    Returns: 4

  11. 3

    1

    Returns: 1

  12. 3

    2

    Returns: 2

  13. 3

    3

    Returns: 2

  14. 3

    4

    Returns: 3

  15. 3

    5

    Returns: 3

  16. 3

    6

    Returns: 4

  17. 3

    7

    Returns: 6

  18. 3

    8

    Returns: 6

  19. 3

    9

    Returns: 9

  20. 4

    2

    Returns: 2

  21. 4

    14

    Returns: 12

  22. 6

    4

    Returns: 3

  23. 6

    34

    Returns: 30

  24. 7

    14

    Returns: 6

  25. 7

    37

    Returns: 24

  26. 8

    7

    Returns: 4

  27. 8

    10

    Returns: 5

  28. 9

    39

    Returns: 18

  29. 10

    25

    Returns: 10

  30. 10

    86

    Returns: 60

  31. 10

    91

    Returns: 70

  32. 11

    26

    Returns: 10

  33. 11

    101

    Returns: 66

  34. 12

    92

    Returns: 48

  35. 12

    99

    Returns: 54

  36. 13

    71

    Returns: 30

  37. 14

    57

    Returns: 22

  38. 14

    91

    Returns: 40

  39. 14

    162

    Returns: 100

  40. 15

    114

    Returns: 50

  41. 16

    61

    Returns: 22

  42. 16

    165

    Returns: 81

  43. 19

    174

    Returns: 72

  44. 21

    50

    Returns: 16

  45. 21

    269

    Returns: 126

  46. 22

    51

    Returns: 17

  47. 23

    424

    Returns: 252

  48. 25

    508

    Returns: 300

  49. 26

    146

    Returns: 46

  50. 27

    72

    Returns: 22

  51. 28

    227

    Returns: 76

  52. 28

    301

    Returns: 110

  53. 29

    825

    Returns: 702

  54. 30

    204

    Returns: 63

  55. 30

    338

    Returns: 120

  56. 30

    565

    Returns: 264

  57. 31

    898

    Returns: 660

  58. 34

    104

    Returns: 30

  59. 34

    998

    Returns: 630

  60. 37

    760

    Returns: 323

  61. 41

    1458

    Returns: 924

  62. 44

    1591

    Returns: 930

  63. 70

    4279

    Returns: 2700

  64. 231

    34596

    Returns: 15580

  65. 371

    48194

    Returns: 15120

  66. 570

    287540

    Returns: 182559

  67. 2352

    4873769

    Returns: 3064984

  68. 2425

    3272292

    Returns: 1308040

  69. 5204

    4901191

    Returns: 1189202

  70. 7138

    7971763

    Returns: 1848372

  71. 9657

    50299325

    Returns: 19686152

  72. 10568

    71959037

    Returns: 31975196

  73. 19948

    32109864

    Returns: 6230504

  74. 25825

    23604994

    Returns: 3837483

  75. 27942

    780755364

    Returns: 780755364

  76. 33459

    531309502

    Returns: 192461499

  77. 34847

    1000000000

    Returns: 568585920

  78. 35126

    837648755

    Returns: 388695692

  79. 42527

    1000000000

    Returns: 397689800

  80. 43733

    1000000000

    Returns: 383687808

  81. 61286

    1

    Returns: 1

  82. 70394

    1000000000

    Returns: 251131869

  83. 82006

    1000000000

    Returns: 228139698

  84. 94326

    1

    Returns: 1

  85. 100000

    1

    Returns: 1

  86. 100000

    999999990

    Returns: 204535818

  87. 100000

    999999991

    Returns: 204535818

  88. 100000

    999999992

    Returns: 204535818

  89. 100000

    999999993

    Returns: 204535818

  90. 100000

    999999994

    Returns: 204535818

  91. 100000

    999999995

    Returns: 204535818

  92. 100000

    999999996

    Returns: 204535818

  93. 100000

    999999997

    Returns: 204535818

  94. 100000

    999999998

    Returns: 204535821

  95. 100000

    999999999

    Returns: 204535821

  96. 100000

    1000000000

    Returns: 204535821

  97. 82006

    2

    Returns: 2

  98. 88888

    343434

    Returns: 32566

  99. 47000

    3821

    Returns: 585

  100. 47000

    1000000000

    Returns: 352835627

  101. 100000

    1000000000

    Returns: 204535821

  102. 90000

    90000

    Returns: 9648

  103. 100000

    999999999

    Returns: 204535821

  104. 100000

    999999799

    Returns: 204535782

  105. 40000

    1000000000

    Returns: 433833778

  106. 100000

    35435

    Returns: 4174

  107. 10000

    1000000

    Returns: 132430

  108. 10000

    10000

    Returns: 1358

  109. 10000

    9000

    Returns: 1237

  110. 10000

    100000000

    Returns: 100000000

  111. 9877

    55555555

    Returns: 22539408

  112. 99998

    99999999

    Returns: 13106934

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: