1.
Introduction
2.
The Problem Statement
2.1.
Example
3.
Approach
3.1.
Program
3.1.1.
Input
3.1.2.
Output
3.2.
Time Complexity
3.3.
Space Complexity
4.
FAQs
5.
Key Takeaways
Last Updated: Mar 27, 2024

# N-Dimensional Plane

Ujjawal Gupta
0 upvote

## Introduction

One day, the ninja's teacher gave him an assignment in which he had to calculate the number of ways by which a point â€˜Xâ€™ in an N-Dimensional plane is reachable from the origin in minimum steps.

The above problem is the standard Combinatorics problem. Combinatorics based-coding problems are widely asked in coding contests and various coding interviews.

## The Problem Statement

Given the array â€˜COORDINATESâ€™ of size â€˜Nâ€™ represents the coordinates of a point â€˜Xâ€™ in the N-dimensional plane. Your task is to print the number of ways by which â€˜Xâ€™ is reachable from the origin in the minimum number of steps. In one step, you have to move in such a way that the total distance is reduced by 1.

Note: you have to print the number of ways mod 10^9 +7

### Example

Let a point X = {1,1} in a 2 dimensional plane. There are two ways by which point â€˜Xâ€™ is reachable from origin {0,0}. These are:

• Move 1st step towards x-axis and 2nd step towards the y-axis. Then we can reach to point â€˜Xâ€™ as (0,0) -> (1,0) -> (1,1).
• Move 1st step towards y-axis and 2nd step towards x-axis. Then we can reach to point â€˜Xâ€™ as (0,0) -> (0,1) -> (1,1).

It is not possible to reach point â€˜Xâ€™ in less than 2 steps.

Also see, Euclid GCD Algorithm

## 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;
}``````

#### 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

1. 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.

2. 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.

3. 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â€™.

4. 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).

5. 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!

Live masterclass