Skip to content

Instantly share code, notes, and snippets.

@adamkorg
Last active September 27, 2019 15:57
Show Gist options
  • Save adamkorg/6b5eb2af8d21cf5bdf7acf45fbeb794f to your computer and use it in GitHub Desktop.
Save adamkorg/6b5eb2af8d21cf5bdf7acf45fbeb794f to your computer and use it in GitHub Desktop.
Leetcode 62: Unique Paths - binomial coefficient optimised
#include <iostream>
using namespace std;
long long factorial(int n) {
long long fact = 1;
for (int i=2; i<=n; ++i)
fact *= i;
return fact;
}
int uniquePath(int m, int n) {
int mx = max(m-1, n-1);
int mn = min(m-1, n-1);
long long dividend = 1;
for (int i=1; i<=mn; ++i)
dividend *= (mx+i);
long long ret = dividend / factorial(mn);
return (int)ret;
}
int main() {
cout << uniquePath(23,12) << "\n";
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment