Approach
The minimum number of steps is the same as the shortest path between origin and ‘X’, the sum of the absolute difference between the coordinates of ‘X’ and origin. All the coordinates of the origin are 0 so we can say that the minimum number of steps say ‘TOTAL’ to reach point ‘X’ is the absolute sum of all the coordinates of point ‘X’. The number of ways to choose the first coordinate is the combination of ‘TOTAL’ and the absolute value of the first coordinate ‘COORDINATE[0]’. Then ‘TOTAL’ is reduced by ‘COORDINATES[0]’ as now we need to calculate the number of ways for the remaining coordinates. Repeat this step for all the coordinates.
Program
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#define MOD 1000000007
using namespace std;
/* Create an array to store the factorial of numbers. */
long long fact[2 * 100000];
/* Function to calculate x^pow. */
long long fastpow(long long x, long long pow)
{
long long ret = 1;
/* Iterative way. */
while (pow)
{
if (pow & 1)
ret = (ret * x) % MOD;
pow /= 2;
x = (x * x) % MOD;
}
return ret;
}
/* Modulo inverse function with respect to MOD. */
long long modInv(long long x)
{
return fastpow(x, MOD - 2);
}
/* Function to update the value of fact. */
void factorial()
{
fact[0] = 1;
for (int i = 1; i < 200000; i++)
{
fact[i] = (fact[i - 1] * i);
fact[i] %= MOD;
}
}
/* Function Definition which return minimum number of ways. */
long long minimumNumberOfWays(long long n, vector<long long> coordinates)
{
long long total = 0, m = 1;
for (int i = 0; i < n; i++)
{
total += abs(coordinates[i]);
}
for (int i = 0; i < n; i++)
{
long long denominator = (fact[total - abs(coordinates[i]]) * fact[abs(coordinates[i]])) % MOD;
long long ans = (fact[total] * modInv(denominator)) % MOD;
m = (m * ans) % MOD;
total -= coordinates[i];
}
return m%MOD;
}
int main()
{
/* Taking the number of coordinates as an input. */
long long int n;
cin >> n;
vector<long long int> coordinates(n);
for (int i = 0; i < n; i++)
{
cin >> coordinates[i];
}
factorial();
/* Function Call. */
long long ans = minimumNumberOfWays(n, coordinates);
cout << ans << endl;
}
You can also try this code with Online C++ Compiler
Input
2
1 1
Output
2
Time Complexity
O(N), where ‘N’ is the number of coordinates.
Creating and assigning values in the ‘FACT’ array takes constant time and traversing of all the coordinates takes O(N) time. Hence its time complexity is O(N).
Space Complexity
O(1),
As we use constant extra space.
FAQs
-
What is combinatorics?
Combinatorics is the number of ways of choosing some objects out of a collection. It is used to solve the problems related to selection, arrangement, and operation within the finite or discrete system.
-
Which data structure is used in calculating a^b in log(b) time?
Stack is used in calculating a^b in log(b) time. Sometimes recursive stack is also used to calculate a^b in log(b) time.
-
What is the factorial of ‘N’?
The factorial of any non-negative integer ‘N’ is the product of all positive numbers greater than 0 and less than or equal to ‘N’.
-
What are the coordinates of origin in the N-dimensional plane?
All the coordinates of origin in the N-dimensional plane are 0. For example, if N=2 then the coordinates of origin is (0,0).
-
What is Stack?
The stack is the linear data structure that follows the particular order in which operations are performed. The order may be first in last out (FILO) or Last in first out(LIFO).
Key Takeaways
In this blog, we learned about an interesting problem, based on N-dimensional Plane. We solved the problem efficiently using the Combinatorics approach. Another problem involving combinatorics is: here.
Hence learning never stops, and there is a lot more to learn.
So head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, and much more. Till then, Happy Coding!
85+ registered