Given a function f(x, y) and a value z, return all positive integer pairs x and y where f(x,y) == z.

The function is constantly increasing, i.e.:

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

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

The function interface is defined like this:

1 2 3 4 5

interface CustomFunction { public:   // Returns positive integer f(x, y) for any given positive integer x and y.   int f(int x, int y); };

interface CustomFunction {
public:
  // Returns positive integer f(x, y) for any given positive integer x and y.
  int f(int x, int y);
};

For custom testing purposes you’re given an integer function_id and a target z as input, where function_id represent one function from an secret internal list, on the examples you’ll know only two functions from the list.

You may return the solutions in any order.

Example 1:

Input: function_id = 1, z = 5
Output: [[1,4],[2,3],[3,2],[4,1]]
Explanation: function_id = 1 means that f(x, y) = x + y

Example 2:

Input: function_id = 2, z = 5
Output: [[1,5],[5,1]]
Explanation: function_id = 2 means that f(x, y) = x * y

Constraints:
1 <= function_id <= 9
1 <= z <= 100
It’s guaranteed that the solutions of f(x, y) == z will be on the range 1 <= x, y <= 1000
It’s also guaranteed that f(x, y) will fit in 32 bit signed integer if 1 <= x, y <= 1000

Hints:
Loop over 1 ≤ x,y ≤ 1000 and check if f(x,y) == z.

List of Functions:

1. f(x,y) = x + y
2. f(x,y) = xy
3. f(x,y) = x² + y
4. f(x,y) = x + y²
5. f(x,y) = x² + y²
6. f(x,y) = (x + y)²
7. f(x,y) = x³ + y³
8. f(x,y) = x²y
9. f(x,y) = xy²

This particular equation can be solved via Bruteforce, Two Pointer or the Binary Search Algorithms respectively.

Bruteforce Algorithm to Find Solutions to Equation

Given the solution space (integer constraints), we can try every possible integer pair (positive and less than 1000) quickly. The bruteforce algorithm does not take advantage of the fact that the function is constantly increasing (monotone).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

/*
 * // This is the custom function interface.
 * // You should not implement it, or speculate about its implementation
 * class CustomFunction {
 * public:
 *     // Returns f(x, y) for any given positive integers x and y.
 *     // Note that f(x, y) is increasing with respect to both x and y.
 *     // i.e. f(x, y) < f(x + 1, y), f(x, y) < f(x, y + 1)
 *     int f(int x, int y);
 * };
 */
 
class Solution {
public:
    vector<vector<int>> findSolution(CustomFunction& customfunction, int z) {
        vector<vector<int>> r;
        for (int x = 1; x <= 1000; ++ x) {
            for (int y = 1; y <= 1000; ++ y) {
                if (customfunction.f(x, y) == z) {
                    r.push_back({x, y});
                }
            }
        }
        return r;
    }
};

/*
 * // This is the custom function interface.
 * // You should not implement it, or speculate about its implementation
 * class CustomFunction {
 * public:
 *     // Returns f(x, y) for any given positive integers x and y.
 *     // Note that f(x, y) is increasing with respect to both x and y.
 *     // i.e. f(x, y) < f(x + 1, y), f(x, y) < f(x, y + 1)
 *     int f(int x, int y);
 * };
 */

class Solution {
public:
    vector<vector<int>> findSolution(CustomFunction& customfunction, int z) {
        vector<vector<int>> r;
        for (int x = 1; x <= 1000; ++ x) {
            for (int y = 1; y <= 1000; ++ y) {
                if (customfunction.f(x, y) == z) {
                    r.push_back({x, y});
                }
            }
        }
        return r;
    }
};

Considering the custom function takes O(1) complexity, thus we try 1000*1000 different pairs which is still O(1). The bruteforce solution is O(1) time and O(1) space, which is fine in solving this equation.

Two Pointer Algorithm to Solve the Equation

We can speed up the bruteforce by using a two pointer algorithm taking advantage of the fact that the function is constantly increasing. If the evaluation of the custom function is less than the target z value, we increment the left pointer, otherwise if it is larger than the target value, we decrement the right pointer – as long as two pointers are in the range of [1, 1000].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    vector<vector<int>> findSolution(CustomFunction& customfunction, int z) {
        vector<vector<int>> r;
        int low = 1, high = 1000;
        while ((low <= 1000) && (high <= 1000) && (high >= 1)) {
            int v = customfunction.f(low, high);
            if (v == z) {
                r.push_back({low, high});
                low ++;
                high --;
            } else if (v < z) {
                low ++;
            } else {
                high --;
            }
        }
        return r;
    }
};

class Solution {
public:
    vector<vector<int>> findSolution(CustomFunction& customfunction, int z) {
        vector<vector<int>> r;
        int low = 1, high = 1000;
        while ((low <= 1000) && (high <= 1000) && (high >= 1)) {
            int v = customfunction.f(low, high);
            if (v == z) {
                r.push_back({low, high});
                low ++;
                high --;
            } else if (v < z) {
                low ++;
            } else {
                high --;
            }
        }
        return r;
    }
};

The two pointer algorithm skips some integers, and thus may be called a better bruteforce in this case.

Binary Search Algorithm to Compute the Solution to Equation

We can bruteforce the first integer in [1, 1000] which is constant time complexity. And as for the second integer in the pair, we can use binary search algorithm which runs at O(log(1000)) – still constant time – but overall faster O(1000*10) compared to bruteforce O(1000*1000).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    vector<vector<int>> findSolution(CustomFunction& customfunction, int z) {
        vector<vector<int>> r;
        for (int i = 1; i <= 1000; ++ i) {
            int low = 1, high = 1000;
            while (low <= high) {
                int mid = (low + high) / 2; 
                int v = customfunction.f(i, mid);
                if (v == z) {
                    r.push_back({i, mid});
                    break;
                }
                if (v < z) {
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
        }
        return r;
    }
};

class Solution {
public:
    vector<vector<int>> findSolution(CustomFunction& customfunction, int z) {
        vector<vector<int>> r;
        for (int i = 1; i <= 1000; ++ i) {
            int low = 1, high = 1000;
            while (low <= high) {
                int mid = (low + high) / 2; 
                int v = customfunction.f(i, mid);
                if (v == z) {
                    r.push_back({i, mid});
                    break;
                }
                if (v < z) {
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
        }
        return r;
    }
};

–EOF (The Ultimate Computing & Technology Blog) —