Last Updated: 18 Apr, 2021

Defeating Ozymandias

Moderate

Asked in company

Solve now

Problem statement

After a heartbreaking defeat from Ozymandias, Ninja goes to the function God. Ninja knows that the function God has an infinite amount of monotonically increasing hidden function, but God will never disclose the formula of the function. Still, due to the good deeds of Ninja, God can tell him what will be the value of the function on any positive integer x and y, i.e. Ninja can know what the value of f(x, y) is.

To defeat Ozymandias, Ninja needs all the values which satisfy f(x, y) == z.

Help Ninja to find all the positive integers x and y where f(x, y) == z.

Note: here monotonically increasing function f(x, y) means:

f(x, y) < f(x + 1, y)

f(x, y) < f(x, y + 1)

Input Format:

The first line of input contains an integer 'T' representing the number of test cases.

The first line of each test case contains a single integer ‘Z’ representing the function value.

Output Format :

For each test case, return a 2-D array denoting the ‘X’ and ‘Y’ values, respectively.

Return the output in sorted order first based on ‘X’, and if ‘X’ is equal, then based on ‘Y’.

The output for each test case is printed in a separate line.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 5
1 <= Z <= 100
1 <= X,Y <= 2000

Time limit: 1 second

Solve now

Approaches

01 Approach

Here, the idea is to try all possible values of ‘X’ and ‘Y’ and insert the values in the array if F(X, Y) == Z.

Algorithm:

Declare a 2-d array ‘RES’.
Repeat the steps using ‘X’ from 1 to 1000
- Repeat the steps using ‘Y’ from 1 to 1000
  - If (F(X, Y) == Z)
  - RES.push( {X, Y} ).
Return ‘RES’.

Solve now

02 Approach

Here, the idea is to try all possible values of ‘X’ and ‘Y’, but as the function is monotonically increasing, we will use this property and first find the maximum value of ‘Y’ by putting ‘X’:= 1.
And then decrement ‘Y’ and increment ‘X’ and check in function.

Algorithm:

Declare ‘Y’ := 1000 and 2-d array ‘RES’.
Repeat the steps using ’X’ from ‘1’ to ‘1000’
- Repeat the steps until Y >1 and f(X ,Y) > Z:
  - Y--
- If( f(X, Y) == Z) RES.push( {X, Y} ).
Return ‘RES’.

Solve now