Count Integer Pairs I
Problem Statement
Develop a function count_pairs(n: int, limit: int) to determine the number of integer pairs (x, y) such that x + y = n and 0 <= x, y <= limit.
Assume that n >= 0.
Examples
count_pairs(5, 3)returns2:(2, 3),(3, 2)count_pairs(7, 5)returns4:(2, 5),(3, 4),(4, 3),(5, 2)
Follow-up
It’s easy to come up with a quadratic time solution for this problem. But challenge yourself to find a constant time solution.
It’s more of a math problem than a coding one lol.
If n is smaller than or equal to limit, then both x and y are definitely smaller than limit no matter how we split n into x and y. x can take on any value between 0 and n, meaning there are n+1 possible combinations of x and y.
If n is larger than limit, then one of x and y can exceed limit if the other one is too small. Here is an example:
n = 5
limit = 3
x = 1
y = n-x = 4 > limit
Therefore, x and y cannot be too big or too small.
Upper limit: x <= limit
Lower limit: y = n-x <= limit, therefore x >= n-limit
It’s possible that limit < n-limit, or n > 2 * limit.
In this case, no pair of (x, y) can satisfy x + y = n and 0 <= x, y <= limit because the maximum sum of (x, y) is 2 * limit according to the second constraint, which means x and y can never sum up to n.
If n is smaller than or equal to 2 * limit, then x can be any integer between n-limit and limit, which means there are 2 * limit - n + 1 possibilities
In a nutshell, the answer is different depending on the relation between n and limit.
n ∈ [0, limit]: n + 1
n ∈ (limit, 2 * limit]: 2 * limit - n + 1
n ∈ (2 * limit, ∞]: 0
If there were no limits:
x = 0, 1, 2, ... , n
y = n, n-1, n-2, ... , 0
will be the (n+1) solutions
Given there is a limit, x <= limit, which will rule out 2 * (n - limit) solutions (where values of x or y exceed the limit as both are complimentary)
Hence,
Number of solutions = ( n + 1 ) - 2 * (n - limit) = 2 * limit + 1 - n
If the limit < n/2, we have no solution, which is why we should do:
max(2 * limit + 1 - n, 0)