Defeating Ozymandias

Moderate
0/80
Average time to solve is 10m
11 upvotes
Asked in company
Facebook

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)

    • Detailed explanation ( Input/output format, Notes, Images )
    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

    Sample Input 1:

    2
5
10

    Sample Output 1:

    1 4 
2 3 
3 2 
4 1
1 10
2 5 
5 2
10 1

    Explanation of Sample Output 1:

    Test Case 1: The hidden function for this test case is F(x, y) = x + y
and to make F(x, y) == 5,
We have 1 + 4 == 2 + 3 == 3 + 2 == 4 + 1 == 5

Test Case 2: This test case’s hidden function is F(X, Y) = X * Y.
To make F(X, Y) == 10
1 * 10 == 2 * 5 == 5 * 2 == 10 * 1 == 10

    Sample Input 2:

    2
9
6

    Sample Output 2:

    1 8
2 7
3 6
4 5
5 4
6 3
7 2
8 1
1 6
2 3
3 2
6 1
    Hint

    Try to check on all possible ‘X’ and ‘Y’ values as values are not more than 1000. 

    Approaches (2)
    Brute Force

    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’.
    Time Complexity

    O(X * Y), where ‘X’ and ‘Y’ is the maximum value that we can pass in the function.

     

    For each value of ‘X’, we are checking the function on all values of ‘Y’.

    Space Complexity

    O(1)

     

    Since we are not using any extra space for finding out the answer the space complexity will be O(1).

    Code Solution
    (100% EXP penalty)
    Defeating Ozymandias
    Full screen
    Console