Ways to Reach Origin

Problem Overview

From (x, y) each move reduces x by one or y by one, and the walk ends at the origin.

Intuition

From (x, y) each move reduces x by one or y by one, and the walk ends at the origin. Every route therefore uses exactly x moves of one kind and y moves of the other, just in a different order. Counting routes is the same as choosing which of the x + y moves are the x moves, which is the binomial coefficient C(x + y, x). Computing that one number replaces filling a whole table.

Algorithm

1Let n = x + y and k = min(x, y), since C(n, x) equals C(n, y) and the smaller side needs fewer steps.
2Multiply the k numerator terms n minus k plus 1 up to n, reducing modulo 1e9+7 after each step.
3Multiply 1 through k into a denominator the same way.
4The modulus is prime, so the denominator inverse is its power MOD minus 2 by fast exponentiation.
5Return the numerator times that inverse, reduced modulo 1e9+7.

Example Walkthrough

Input: x = 3, y = 6

1. There are 9 moves in total and 3 of them reduce x.
2. The numerator is 7 times 8 times 9, which is 504. The denominator is 1 times 2 times 3, which is 6.
3. 504 divided by 6 gives 84 routes.

Output: 84

Common Pitfalls

• Division does not work directly under a modulus. Multiply by the modular inverse instead.
• Take the remainder after every multiplication, or the product overflows a long.
• When x or y is 0 there is exactly one route, and the loop runs zero times to give 1.
• Filling an x by y table also works but costs quadratic time and memory for the same number.

Ways to Reach Origin.java

Java

// Approach: Every route uses exactly x left steps and y down steps in some
// order, so the count is the binomial C(x + y, k) with k = min(x, y).
// Multiply the k numerator terms and the k denominator terms modulo the
// prime, then divide once with a Fermat inverse.
// Complexity: O(min(x, y) + log MOD) time, O(1) extra space.
class Solution {
    private static final long MOD = 1_000_000_007L;

    public int ways(int x, int y) {
        int n = x + y;
        int k = Math.min(x, y);
        long num = 1;
        long den = 1;
        for (int i = 1; i <= k; i++) {
            num = num * (n - k + i) % MOD;
            den = den * i % MOD;
        }
        return (int) (num * pow(den, MOD - 2) % MOD);
    }

    private long pow(long base, long exp) {
        long result = 1;
        base %= MOD;
        while (exp > 0) {
            if ((exp & 1) == 1)
                result = result * base % MOD;
            base = base * base % MOD;
            exp >>= 1;
        }
        return result;
    }
}

Was this solution helpful?