Count of non decreasing arrays of length N formed with values in range L to R
Given are integers N, L and R, the task is to count the number of non decreasing arrays of length N formed with values in range [L, R] with repetition allowed.
Examples:
Input: N = 4, L = 4, R = 6
Output: 5
All possible arrays are {4, 4, 4, 6}, {4, 4, 5, 6}, {4, 5, 5, 6}, {4, 5, 6, 6} and {4, 6, 6, 6}.
Input: N = 2, L = 5, R = 2
Output: 0
No such combinations exist as L > R.
Approach:
- Since it is known that the minimum number is L and maximum number is R in the array.
- If the remaining (N – 2) indices are filled with L, the minimum possible sum is obtained and if the remaining (N-2) indices are filled with R, the maximum possible sum is obtained.
- It can be concluded that there exists a combination of numbers which results in a sum in between the minimum possible and maximum possible sum.
- Therefore, total different number of sums can be computed by:
[(N – 2) * R – (N – 2) * L] + 1 = (N – 2) * (R – L) + 1
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the count // of different arrays int countSum( int N, int L, int R) { // No such combination exists if (L > R) { return 0; } // Arrays formed with single elements if (N == 1) { return R - L + 1; } if (N > 1) { return (N - 2) * (R - L) + 1; } } // Driver code int main() { int N = 4, L = 4, R = 6; cout << countSum(N, L, R); return 0; } |
Java
// Java implementation of the approach class GFG { // Function to return the count // of different arrays static int countSum( int N, int L, int R) { // No such combination exists if (L > R) { return 0 ; } // Arrays formed with single elements if (N == 1 ) { return R - L + 1 ; } if (N > 1 ) { return (N - 2 ) * (R - L) + 1 ; } return 0 ; } // Driver code public static void main(String[] args) { int N = 4 , L = 4 , R = 6 ; System.out.print(countSum(N, L, R)); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 implementation of the approach # Function to return the count # of different arrays def countSum(N, L, R): # No such combination exists if (L > R): return 0 ; # Arrays formed with single elements if (N = = 1 ): return R - L + 1 ; if (N > 1 ): return (N - 2 ) * (R - L) + 1 ; return 0 ; # Driver code if __name__ = = '__main__' : N, L, R = 4 , 4 , 6 ; print (countSum(N, L, R)); # This code is contributed by 29AjayKumar |
C#
// C# implementation of the approach using System; class GFG { // Function to return the count // of different arrays static int countSum( int N, int L, int R) { // No such combination exists if (L > R) { return 0; } // Arrays formed with single elements if (N == 1) { return R - L + 1; } if (N > 1) { return (N - 2) * (R - L) + 1; } return 0; } // Driver code public static void Main(String[] args) { int N = 4, L = 4, R = 6; Console.Write(countSum(N, L, R)); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // Javascript implementation of the approach // Function to return the count // of different arrays function countSum(N, L, R) { // No such combination exists if (L > R) { return 0; } // Arrays formed with single elements if (N == 1) { return R - L + 1; } if (N > 1) { return (N - 2) * (R - L) + 1; } } // Driver code var N = 4, L = 4, R = 6; document.write( countSum(N, L, R)); // This code is contributed by noob2000. </script> |
Output:
5
Time Complexity: O(1)
Auxiliary Space: O(1), no extra space is required, so it is a constant.