We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Positive Integer Solution for a Given Equation

Number: 1358

Difficulty: Medium

Paid? No

Companies: TikTok, Google

Problem Description

Given a hidden function f(x, y) that is monotonically increasing with respect to both x and y, find all positive integer pairs (x, y) such that f(x, y) equals a target value z. The function satisfies:

  • f(x, y) < f(x + 1, y)
  • f(x, y) < f(x, y + 1) You can assume that the valid pairs (x, y) lie within the range [1, 1000].

Key Insights

  • The function is monotonic in both variables, which allows us to narrow down the search.
  • By iterating over one variable (say x) and performing a binary search for the other variable (y), we can efficiently find the solution.
  • If f(x, mid) is less than z, then increasing mid (i.e., y) might yield z; if it is more, we decrease mid.
  • The search space is limited to 1 to 1000, ensuring that the binary search runs in log(1000) steps for each x.

Space and Time Complexity

Time Complexity: O(1000 * log(1000))
Space Complexity: O(1) (ignoring the space required for the output)

Solution

We solve the problem by iterating x from 1 to 1000. For each x, we use binary search on y (ranging from 1 to 1000) to find a value such that f(x, y) equals z. Because the function f is monotonically increasing with respect to y, binary search is applicable. For each x, if we find a y that satisfies the equation, we add the pair (x, y) to the result.

Code Solutions

# Python solution with line-by-line comments
def findSolution(customfunction, z):
    result = []  # List to store the valid pairs of (x, y)
    # Iterate over possible x values from 1 to 1000
    for x in range(1, 1001):
        low, high = 1, 1000  # Set the search range for y
        # Apply binary search on y for the current x
        while low <= high:
            mid = (low + high) // 2  # Middle value in the current range for y
            value = customfunction.f(x, mid)  # Compute f(x, mid)
            if value == z:  # If the value matches target z
                result.append([x, mid])  # Add this pair to result
                break  # No need to search further for this x
            elif value < z:  # If computed value is less than z, search in higher half
                low = mid + 1
            else:  # If computed value is greater than z, search in lower half
                high = mid - 1
    return result  # Return all the valid (x, y) pairs
← Back to All Questions