Intuition:
The above statement is an interesting problem related to mathematics that can be easily solved with the help of combinatorics and implementation.
The case when the number of elements in the range [L, R] are less than ‘N’ elements can be considered as a trivial case where the answer will always be zero. Now in the other cases, when the number of elements in the given range are not sufficient to satisfy the second condition of consecutive differences, then also the number of ways to select ‘N’ integers will be zero.
For the other cases, we can just remove the elements which cannot be selected as the last element selected is having a difference greater than the current element of the array ARR[], and select a combination of ‘N’ elements from the rest of the elements.
Let’s understand the further solution in the algorithm.
Algorithm
- First, input of ‘N’, ‘L’, ‘R’, and ARR[], will be taken in the main function.
- Now, we will check if the elements in the range are less than the required numbers and output ‘0’, if found insufficient.
- Then as the number of elements are enough to be chosen, we will simply find the combinations of ‘N’ elements out of the left elements with the help of function nCr().
Following is the implementation of the above algorithm.
Implementation
// Program to find numbers in a range.
#include <iostream>
#include <vector>
using namespace std;
#define MOD 1000000007
#define W 2000001
// Vector to store the factorials.
vector<long long> fac(W);
// Function to store factorials.
void pre(long long n)
{
fac[0] = 1;
for (int i = 1; i <= n; i++)
fac[i] = (fac[i - 1] * i) % MOD;
}
// Function for Binary Exponentiation.
long long power(long long x, long long y)
{
long long res = 1;
x = x % MOD;
while (y > 0)
{
if (y & 1)
res = (res * x) % MOD;
y = y >> 1;
x = (x * x) % MOD;
}
return res;
}
// Function to find modulo inverse.
long long modInverse(long long n, int M)
{
return power(n, M - 2);
}
// Function to find number of combinations.
long long nCr(long long n, long long r)
{
// If n<r, then nCr must return 0.
if (n < r)
return 0;
// Covering the base case.
if (r == 0)
return 1;
// Final nCr.
return (fac[n] % MOD * (modInverse(fac[r], MOD) % MOD * modInverse(fac[n - r], MOD) % MOD)) % MOD;
}
// Main Function.
int main()
{
// Input of variables provided.
long long N, L, R;
cin >> N >> L >> R;
vector<long long> ARR(N);
for (int i = 1; i < N; ++i)
cin >> ARR[i];
/*
Checking if the number of elements
in the range are sufficient.
*/
long long cnt = R - L - N + 1;
for (int i = 1; i < N; ++i)
{
cnt -= max((long long)0, ARR[i] - 1);
}
// variable to store the final answer.
long long ans = 0;
/*
If the number of elements are more than
or equal to required elements, output 0.
*/
if (cnt >= 0)
{
pre(cnt + N + 1);
ans = nCr(N + cnt, N);
}
// Output of final answer.
cout << ans;
return 0;
}
Example
Input
6 12 25
1 2 3 4 2
Output
7
Complexity Analysis
Time Complexity
O(max(N, M)), where ‘N’ is the number of elements to be chosen from the given range and ‘M’ is the total number of elements in the range [L, R].
Explanation: Checking if it is possible to select ‘N’ elements with required conditions takes a total of O(N) time for running a for loop from 1 to ‘N’. And in calculating the factorials in pre() function, the total time consumed will be O(M), where ‘M’ is the total number of elements in the range [L, R].
Space complexity:
O(M), where ‘M’ is the total number of elements in the range [L, R].
Explanation: The vector used to store the factorials occupies O(M) of total space.
FAQs
-
Why the answer is required to get modulo of ‘1e9 + 7’?
As the number of ways can get very huge and can exceed the integer limit, thus to make it stay inside the integer limit we have to take its modulo.
-
Why are we using ‘long long’ in place of ‘int’ in the program?
While calculating the number of ways, the number will exceed the int limit before taking modulo, and the program on execution will give a verdict of runtime error. Thus to avoid such interruptions, we just use ‘long long’.
-
What is the use of inverse modulo in calculating the combinations?
In the formula of nCr, we are taking the modulo of numerator and denominator both, due to which many complications get involved. So to get rid of these complications, we use inverse modulo.
-
Why is binary exponentiation used in place of normal exponentiation?
The time complexity of the normal exponential function is linear whereas the time complexity of binary exponentiation is logarithmic. So to make our code more efficient, binary exponentiation is used in place of normal exponentiation.
-
Is there any better way to calculate the factorials than the above-mentioned approach?
No, there isn’t any better way to calculate the factorials than the above-mentioned approach. The best time complexity for calculating factorials is linear.
Key Takeaways
The above blog has covered an important and interesting problem related to Data Structures & Algorithms and Combinatorics which helps you enhance your problem-solving skills. It also helps us to learn the way to calculate nCr and inverse modulo with the help of binary exponentiation.
Find more such interesting questions on our practice platform Coding Ninjas Studio if you want to learn more before jumping into practicing, head over to our library section for many such interesting blogs. Keep learning.
Happy Coding!
38+ registered 