TCHS-9-1000

Problem Statement

Consider a square n x n matrix A. The cell A_i,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 n². 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

0)

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}.

1)

2

4

Returns: 4

k is 1-based.

2)

3

8

Returns: 6

3)

1

1

Returns: 1

4)

4

4

Returns: 3

public class ProductsMatrix {

	long N;
	
	public long nthElement(int n, int k) {
		N = n;
		long low = 1L, high = (n + 0L) * n;
		while (low < high) {
			long mid = low + (high - low) / 2;
			if (indexOf(mid) < k)
				low = mid + 1;
			else
				high = mid;
		}
		return low;
	}
	
	private long indexOf(long x) {
		long sum = 0;
		for (long i = 1; i <= N; i++)
			sum += (i * N <= x) ? N : x / i;
		return sum;
	}

}