Given three integers N, L, and R, the task is to print the total count of ways to form a necklace of at most N pearls such that the values of a pearl lie in the range [L, R] and are in ascending order.
Examples:
Input: N = 3, L = 6, R = 9
Output: 34
Explanation:
The necklace can be formed in the following ways:
- The necklaces of length one that can be formed are { “6”, “7”, “8”, “9” }.
- The necklaces of length two, that can be formed are { “66”, “67”, “68”, “69”, “77”, “78”, “79”, “88”, “89”, “99” }.
- The necklaces of length three, that can be formed are { “666”, “667”, “668”, “669”, “677”, “678”, “679”, “688”, “689”, “699”, “777”, “778”, “779”, “788”, “789”, “799”, “888”, “889”, “899”, “999” }.
Thus, in total, the necklace can be formed in (4+10+20 = 34 ) ways.
Input: N = 1, L = 8, R = 9
Output: 2
Explanation:
The necklace can be formed in the following ways: {“8”, “9”}.
Approach: The given problem can be solved based on the following observations:
- The problem can be solved using 2 states dynamic programming with prefix sum.
- Suppose Dp(i, j) stores the count of ways to form a necklace of size i with values of pearls in the range [L, j].
- Then the transition state at the ith position can be defined as:
- For each value j in the range [L, R],
- Dp(i, j) = Dp(i – 1, L) + Dp(i – 1, L + 1), …, Dp(i – 1, j – 1)+ Dp(i – 1, j)
- For each value j in the range [L, R],
- The above transition can be optimized by using prefix sum for every i as:
- Dp(i, j) = Dp(i, L) + Dp(i, L + 1) +…+ Dp(i, j – 1) + Dp(i, j)
- Therefore, now transitions can be defined as:
- Dp(i, j) = Dp(i-1, j) + Dp(i, j-1)
Follow the steps below to solve the problem:
- Initialize a variable, say ans as 0, to store the result.
- Initialize a 2D array, say Dp[][] of dimension N * (R – L + 1) as 0 to store all the DP-states.
- Iterate over the range [0, N – 1] using the variable i, and assign Dp[i][0] = 1.
- Iterate over the range [1, R – L] using the variable i, and update the Dp[0][i] as Dp[0][i]= Dp[0][i – 1]+1.
- Assign Dp[0][R – L] to ans.
- Iterate over the range [1, N – 1] using the variable i, and perform the following operations:
- Iterate over the range [1, R – L] using the variable j, and update the Dp[i][j] as Dp[i][j] = Dp[i][j – 1] + Dp[i – 1][j].
- Increment the ans by Dp[i][R – L].
- Finally, after completing the above steps, print the ans.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count total number of waysint Count(int N, int L, int R){ // Stores all DP-states vector<vector<int> > dp(N, vector<int>(R - L + 1, 0)); // Stores the result int ans = 0; // Traverse the range [0, N] for (int i = 0; i < N; i++) { dp[i][0] = 1; } // Traverse the range [1, R - L] for (int i = 1; i < dp[0].size(); i++) { // Update dp[i][j] dp[0][i] = dp[0][i - 1] + 1; } // Assign dp[0][R-L] to ans ans = dp[0][R - L]; // Traverse the range [1, N] for (int i = 1; i < N; i++) { // Traverse the range [1, R - L] for (int j = 1; j < dp[0].size(); j++) { // Update dp[i][j] dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } // Increment ans by dp[i-1][j] ans += dp[i][R - L]; } // Return ans return ans;}// Driver Codeint main(){ // Input int N = 3; int L = 6; int R = 9; // Function call cout << Count(N, L, R); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{ // Function to count total number of waysstatic int Count(int N, int L, int R){ // Stores all DP-states int[][] dp = new int[N][R - L + 1]; // Stores the result int ans = 0; // Traverse the range [0, N] for(int i = 0; i < N; i++) { dp[i][0] = 1; } // Traverse the range [1, R - L] for(int i = 1; i < dp[0].length; i++) { // Update dp[i][j] dp[0][i] = dp[0][i - 1] + 1; } // Assign dp[0][R-L] to ans ans = dp[0][R - L]; // Traverse the range [1, N] for(int i = 1; i < N; i++) { // Traverse the range [1, R - L] for(int j = 1; j < dp[0].length; j++) { // Update dp[i][j] dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } // Increment ans by dp[i-1][j] ans += dp[i][R - L]; } // Return ans return ans;}// Driver Codepublic static void main(String args[]){ // Input int N = 3; int L = 6; int R = 9; // Function call System.out.println(Count(N, L, R));}}// This code is contributed by avijitmondal1998 |
Python3
# Python3 program for the above approach# Function to count total number of waysdef Count(N, L, R): # Stores all DP-states dp = [[0 for i in range(R - L + 1)] for i in range(N)] # Stores the result ans = 0 # Traverse the range [0, N] for i in range(N): dp[i][0] = 1 # Traverse the range [1, R - L] for i in range(1, len(dp[0])): # Update dp[i][j] dp[0][i] = dp[0][i - 1] + 1 # Assign dp[0][R-L] to ans ans = dp[0][R - L] # Traverse the range [1, N] for i in range(1, N): # Traverse the range [1, R - L] for j in range(1, len(dp[0])): # Update dp[i][j] dp[i][j] = dp[i - 1][j] + dp[i][j - 1] # Increment ans by dp[i-1][j] ans += dp[i][R - L] # Return ans return ans# Driver Codeif __name__ == '__main__': # Input N = 3 L = 6 R = 9 # Function call print(Count(N, L, R)) # This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;class GFG{// Function to count total number of waysstatic int Count(int N, int L, int R){ // Stores all DP-states int[,] dp = new int[N, R - L + 1]; // Stores the result int ans = 0; // Traverse the range [0, N] for(int i = 0; i < N; i++) { dp[i, 0] = 1; } // Traverse the range [1, R - L] for(int i = 1; i < dp.GetLength(1); i++) { // Update dp[i][j] dp[0, i] = dp[0, i - 1] + 1; } // Assign dp[0][R-L] to ans ans = dp[0, R - L]; // Traverse the range [1, N] for(int i = 1; i < N; i++) { // Traverse the range [1, R - L] for(int j = 1; j < dp.GetLength(1); j++) { // Update dp[i][j] dp[i, j] = dp[i - 1, j] + dp[i, j - 1]; } // Increment ans by dp[i-1][j] ans += dp[i, R - L]; } // Return ans return ans;}// Driver Codepublic static void Main(){ // Input int N = 3; int L = 6; int R = 9; // Function call Console.Write(Count(N, L, R));}}// This code is contributed by ukasp |
Javascript
<script>// Javascript program for the above approach// Function to count total number of waysfunction Count(N, L, R) { // Stores all DP-states let dp = new Array(N).fill(0).map(() => new Array(R - L + 1).fill(0)); // Stores the result let ans = 0; // Traverse the range [0, N] for (let i = 0; i < N; i++) { dp[i][0] = 1; } // Traverse the range [1, R - L] for (let i = 1; i < dp[0].length; i++) { // Update dp[i][j] dp[0][i] = dp[0][i - 1] + 1; } // Assign dp[0][R-L] to ans ans = dp[0][R - L]; // Traverse the range [1, N] for (let i = 1; i < N; i++) { // Traverse the range [1, R - L] for (let j = 1; j < dp[0].length; j++) { // Update dp[i][j] dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } // Increment ans by dp[i-1][j] ans += dp[i][R - L]; } // Return ans return ans;}// Driver Code// Inputlet N = 3;let L = 6;let R = 9;// Function calldocument.write(Count(N, L, R));// This code is contributed by _saurabh_jaiswal.</script> |
Output
34
Time Complexity: O(N * (R – L))
Auxiliary Space: O(N * (R – L))
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
