How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Microsoft.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Microsoft during technical interviews.

Count integer pairs satisfying 1/x + 1/y = 1/N

Company: Microsoft

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

You are given a positive integer `N` (\(1 \le N \le 10^6\)). Consider the Diophantine equation: \[ \frac{1}{x} + \frac{1}{y} = \frac{1}{N}, \] where `x` and `y` are positive integers. Determine **how many ordered pairs** of positive integers `(x, y)` satisfy this equation. Formally, count the number of pairs `(x, y)` with `x > 0`, `y > 0`, and \[ \frac{1}{x} + \frac{1}{y} = \frac{1}{N}. \] Output this count for the given `N`. Your algorithm should be efficient enough to handle values up to `N = 10^6`.

Quick Answer: This question evaluates understanding of number theory and algorithmic problem-solving, focusing on Diophantine equation manipulation, divisor counting, and translating algebraic constraints into combinatorial counts.

You are given a positive integer N (1 <= N <= 10^6). Count how many **ordered** pairs of positive integers (x, y) satisfy the equation: 1/x + 1/y = 1/N with x > 0 and y > 0. **Examples** - N = 1: the only solution is (2, 2), so the answer is 1. - N = 2: the ordered pairs are (3, 6), (4, 4), (6, 3), so the answer is 3. - N = 4: the answer is 5. **Hint on the math:** Rewrite the equation. Multiplying through and rearranging, with x = N + a and y = N + b, the condition becomes a*b = N^2 for positive integers a, b. Each ordered factorization of N^2 gives exactly one ordered pair (x, y). Therefore the answer equals the number of positive divisors of N^2. If N = p1^e1 * p2^e2 * ... then N^2 = p1^(2*e1) * ..., and the divisor count is the product of (2*ei + 1) over all prime factors. Return the count.

Constraints

1 <= N <= 10^6
x and y are positive integers
Count ordered pairs: (x, y) and (y, x) are counted separately when x != y

Examples

Input: (1,)

Expected Output: 1

Explanation: N=1: only pair is (2,2). N^2=1 has 1 divisor.

Input: (2,)

Expected Output: 3

Explanation: N=2: pairs (3,6),(4,4),(6,3). N^2=4 has divisors 1,2,4 -> 3.

Input: (4,)

Expected Output: 5

Explanation: N=4=2^2, N^2=2^4 has 5 divisors -> 5 ordered pairs.

Input: (6,)

Expected Output: 9

Explanation: N=6=2*3, divisor count = (2*1+1)(2*1+1) = 3*3 = 9.

Input: (12,)

Expected Output: 15

Explanation: N=12=2^2*3, count = (2*2+1)(2*1+1) = 5*3 = 15.

Input: (360,)

Expected Output: 105

Explanation: N=360=2^3*3^2*5, count = 7*5*3 = 105.

Input: (999983,)

Expected Output: 3

Explanation: 999983 is prime, so N^2=p^2 has 3 divisors -> 3.

Input: (1000000,)

Expected Output: 169

Explanation: N=10^6=2^6*5^6, count = (2*6+1)(2*6+1) = 13*13 = 169 (upper bound case).

Hints

Manipulate 1/x + 1/y = 1/N algebraically. With x = N + a and y = N + b, the equation reduces to a*b = N^2.
Every positive divisor a of N^2 yields exactly one valid ordered pair, so the answer is the number of positive divisors of N^2.
If N = product of p_i^e_i, then N^2 = product of p_i^(2*e_i), and the divisor count is the product of (2*e_i + 1). Factor N by trial division up to sqrt(N).

Quick Overview

This question evaluates understanding of number theory and algorithmic problem-solving, focusing on Diophantine equation manipulation, divisor counting, and translating algebraic constraints into combinatorial counts.