Given an array arr[] having N positive integers and a positive integers H, the task is to count the maximum occurrences of a value from the range [L, R] on adding arr[i] or arr[i] – 1 to X (initially 0). The integer X must be always be less than H. If it is greater than H, replace X by X % H
Examples:
Input: arr = {16, 17, 14, 20, 20, 11, 22}, H = 24, L = 21, R = 23
Output: 3
Explanation:
Initially X = 0.
Then add arr[0] – 1 to X, now the X is 15. This X is not good.
Then add arr[1] – 1 to X, now the X is 15 + 16 = 31. 31 % H = 7. This X is also not good.
Then add arr[2] to X, now the X is 7 + 14 = 21. This X is good.
Then add arr[3] – 1 to X, now the X is (21 + 19) % H = 16. This X is not good.
Then add arr[4] to X, now the X is (16 + 20) % H = 12. This X is not good.
Then add arr[5] to X, now the X is 12 + 11 = 23. This X is good.
Then add arr[6] to X, now the X is 23 + 22 = 21. This X is also good.
So, the maximum number of good X in the example is 3.Input: arr = {1, 2, 3}, H = 5, L = 1, R = 2
Output: 2
Approach: This problem can be solved with dynamic programming. Maintain a table dp[N+1][H] which represents the maximum occurrences of an element in the range [L, R] on adding upto i elements. For every ith index, calculate the maximum possible frequency obtainable by adding arr[i] and arr[i] – 1. Once, computed for all indices, find the maximum from the last row of the dp[][] matrix.
Below is the implementation of above approach:
C++
// C++ implementation of the// above approach#include <bits/stdc++.h>using namespace std;// Function that prints the number// of times X gets a value// between L and Rvoid goodInteger(int arr[], int n, int h, int l, int r){ vector<vector<int> > dp( n + 1, vector<int>(h, -1)); // Base condition dp[0][0] = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < h; j++) { // Condition if X can be made // equal to j after i additions if (dp[i][j] != -1) { // Compute value of X // after adding arr[i] int h1 = (j + arr[i]) % h; // Compute value of X after // adding arr[i] - 1 int h2 = (j + arr[i] - 1) % h; // Update dp as the maximum value dp[i + 1][h1] = max(dp[i + 1][h1], dp[i][j] + (h1 >= l && h1 <= r)); dp[i + 1][h2] = max(dp[i + 1][h2], dp[i][j] + (h2 >= l && h2 <= r)); } } } int ans = 0; // Compute maximum answer from all // possible cases for (int i = 0; i < h; i++) { if (dp[n][i] != -1) ans = max(ans, dp[n][i]); } // Printing maximum good occurrence of X cout << ans << "\n";}// Driver Codeint main(){ int A[] = { 16, 17, 14, 20, 20, 11, 22 }; int H = 24; int L = 21; int R = 23; int size = sizeof(A) / sizeof(A[0]); goodInteger(A, size, H, L, R); return 0;} |
Java
// Java implementation of the// above approachclass GFG{// Function that prints the number// of times X gets a value// between L and Rstatic void goodInteger(int arr[], int n, int h, int l, int r){ int [][]dp = new int[n + 1][h]; for(int i = 0; i < n; i++) for(int j = 0; j < h; j++) dp[i][j] = -1; // Base condition dp[0][0] = 0; for(int i = 0; i < n; i++) { for(int j = 0; j < h; j++) { // Condition if X can be made // equal to j after i additions if (dp[i][j] != -1) { // Compute value of X // after adding arr[i] int h1 = (j + arr[i]) % h; // Compute value of X after // adding arr[i] - 1 int h2 = (j + arr[i] - 1) % h; // Update dp as the maximum value dp[i + 1][h1] = Math.max(dp[i + 1][h1], dp[i][j] + ((h1 >= l && h1 <= r) ? 1 : 0)); dp[i + 1][h2] = Math.max(dp[i + 1][h2], dp[i][j] + ((h2 >= l && h2 <= r) ? 1 : 0)); } } } int ans = 0; // Compute maximum answer from all // possible cases for(int i = 0; i < h; i++) { if (dp[n][i] != -1) ans = Math.max(ans, dp[n][i]); } // Printing maximum good occurrence of X System.out.print(ans + "\n");}// Driver Codepublic static void main(String[] args){ int A[] = { 16, 17, 14, 20, 20, 11, 22 }; int H = 24; int L = 21; int R = 23; int size = A.length; goodInteger(A, size, H, L, R);}}// This code is contributed by 29AjayKumar |
Python3
# Python3 implementation of the above approach# Function that prints the number# of times X gets a value# between L and Rdef goodInteger(arr, n, h, l, r): dp = [[-1 for i in range(h)] for j in range(n + 1)] # Base condition dp[0][0] = 0 for i in range(n): for j in range(h): # Condition if X can be made # equal to j after i additions if(dp[i][j] != -1): # Compute value of X # after adding arr[i] h1 = (j + arr[i]) % h # Compute value of X after # adding arr[i] - 1 h2 = (j + arr[i] - 1) % h # Update dp as the maximum value dp[i + 1][h1] = max(dp[i + 1][h1], dp[i][j] + (h1 >= l and h1 <= r)) dp[i + 1][h2] = max(dp[i + 1][h2], dp[i][j] + (h2 >= l and h2 <= r)) ans = 0 # Compute maximum answer from all # possible cases for i in range(h): if(dp[n][i] != -1): ans = max(ans, dp[n][i]) # Printing maximum good occurrence of X print(ans)# Driver Codeif __name__ == '__main__': A = [ 16, 17, 14, 20, 20, 11, 22 ] H = 24 L = 21 R = 23 size = len(A) goodInteger(A, size, H, L, R)# This code is contributed by Shivam Singh |
C#
// C# implementation of the // above approach using System;class GFG{ // Function that prints the number // of times X gets a value // between L and R static void goodint(int []arr, int n, int h, int l, int r) { int [,]dp = new int[n + 1, h]; for(int i = 0; i < n; i++) for(int j = 0; j < h; j++) dp[i, j] = -1; // Base condition dp[0, 0] = 0; for(int i = 0; i < n; i++) { for(int j = 0; j < h; j++) { // Condition if X can be made // equal to j after i additions if (dp[i, j] != -1) { // Compute value of X // after adding arr[i] int h1 = (j + arr[i]) % h; // Compute value of X after // adding arr[i] - 1 int h2 = (j + arr[i] - 1) % h; // Update dp as the maximum value dp[i + 1, h1] = Math.Max(dp[i + 1, h1], dp[i, j] + ((h1 >= l && h1 <= r) ? 1 : 0)); dp[i + 1, h2] = Math.Max(dp[i + 1, h2], dp[i, j] + ((h2 >= l && h2 <= r) ? 1 : 0)); } } } int ans = 0; // Compute maximum answer from all // possible cases for(int i = 0; i < h; i++) { if (dp[n, i] != -1) ans = Math.Max(ans, dp[n, i]); } // Printing maximum good occurrence of X Console.Write(ans + "\n"); } // Driver Code public static void Main(String[] args) { int []A = { 16, 17, 14, 20, 20, 11, 22 }; int H = 24; int L = 21; int R = 23; int size = A.Length; goodint(A, size, H, L, R); } } // This code is contributed by Rajput-Ji |
Javascript
<script>// JavaScript implementation of the// above approach// Function that prints the number// of times X gets a value// between L and Rfunction goodInteger(arr, n, h, l, r){ let dp = new Array(n + 1); for(var i = 0; i < dp.length; i++) { dp[i] = new Array(2); } for(let i = 0; i < n+1; i++) for(let j = 0; j < h; j++) dp[i][j] = -1; // Base condition dp[0][0] = 0; for(let i = 0; i < n; i++) { for(let j = 0; j < h; j++) { // Condition if X can be made // equal to j after i additions if (dp[i][j] != -1) { // Compute value of X // after adding arr[i] let h1 = (j + arr[i]) % h; // Compute value of X after // adding arr[i] - 1 let h2 = (j + arr[i] - 1) % h; // Update dp as the maximum value dp[i + 1][h1] = Math.max(dp[i + 1][h1], dp[i][j] + ((h1 >= l && h1 <= r) ? 1 : 0)); dp[i + 1][h2] = Math.max(dp[i + 1][h2], dp[i][j] + ((h2 >= l && h2 <= r) ? 1 : 0)); } } } let ans = 0; // Compute maximum answer from all // possible cases for(let i = 0; i < h; i++) { if (dp[n][i] != -1) ans = Math.max(ans, dp[n][i]); } // Printing maximum good occurrence of X document.write(ans + "\n");} // Driver Codelet A = [ 16, 17, 14, 20, 20, 11, 22 ];let H = 24;let L = 21;let R = 23;let size = A.length;goodInteger(A, size, H, L, R);// This code is contributed by sanjoy_62 </script> |
Output
3
Time Complexity: O(N * H)
Auxiliary Space: O(N*H)
Efficient approach: Space optimization
In previous approach, the current value dp[i][j] is only depend upon the current and previous row values of DP. So to optimize the space complexity we use a single 1D array to store the computations.
Implementation steps:
- Create a 1D vector dp of size h and initialize it with -1.
- Set a base case by initializing the values of dp, dp[0] = 0.
- Now iterate over subproblems by the help of nested loop and get the current value from previous computations.
- Now Create a temporary 1d vector new_dp used to store the current values from previous computations.
- After every iteration assign the value of new_dp to dp for further iteration.
- Initialize a variable ans to store the final answer and update it by iterating through the Dp.
- At last print the final answer stored in ans .
Implementation:
C++
// C++ implementation of the// above approach#include <bits/stdc++.h>using namespace std;// Function that prints the number// of times X gets a value// between L and Rvoid goodInteger(int arr[], int n, int h, int l, int r){ // initialize DP vector<int> dp(h, -1); // Base condition dp[0] = 0; for (int i = 0; i < n; i++) { vector<int> new_dp(h, -1); for (int j = 0; j < h; j++) { if (dp[j] != -1) { int h1 = (j + arr[i]) % h; int h2 = (j + arr[i] - 1) % h; new_dp[h1] = max(new_dp[h1], dp[j] + (h1 >= l && h1 <= r)); new_dp[h2] = max(new_dp[h2], dp[j] + (h2 >= l && h2 <= r)); } } dp = new_dp; } int ans = 0; // Compute maximum answer from all // possible cases for (int i = 0; i < h; i++) { ans = max(ans, dp[i]); } // Printing maximum good occurrence of X cout << ans << "\n";}// Driver Codeint main(){ int A[] = { 16, 17, 14, 20, 20, 11, 22 }; int H = 24; int L = 21; int R = 23; int size = sizeof(A) / sizeof(A[0]); goodInteger(A, size, H, L, R); return 0;}// this code is contributed by bhardwajji |
Java
import java.util.*;public class Main { // Function that prints the number // of times X gets a value // between L and R static void goodInteger(int[] arr, int n, int h, int l, int r) { // initialize DP List<Integer> dp = new ArrayList<>(Collections.nCopies(h, -1)); // Base condition dp.set(0, 0); for (int i = 0; i < n; i++) { List<Integer> new_dp = new ArrayList<>( Collections.nCopies(h, -1)); for (int j = 0; j < h; j++) { if (dp.get(j) != -1) { int h1 = (j + arr[i]) % h; int h2 = (j + arr[i] - 1) % h; new_dp.set( h1, Math.max(new_dp.get(h1), dp.get(j) + (h1 >= l && h1 <= r ? 1 : 0))); new_dp.set( h2, Math.max(new_dp.get(h2), dp.get(j) + (h2 >= l && h2 <= r ? 1 : 0))); } } dp = new_dp; } int ans = 0; // Compute maximum answer from all // possible cases for (int i = 0; i < h; i++) { ans = Math.max(ans, dp.get(i)); } // Printing maximum good occurrence of X System.out.println(ans); } // Driver Code public static void main(String[] args) { int[] A = { 16, 17, 14, 20, 20, 11, 22 }; int H = 24; int L = 21; int R = 23; int size = A.length; goodInteger(A, size, H, L, R); }} |
Python3
# Python 3 implementation of the# above approach# Function that prints the number# of times X gets a value# between L and Rdef goodInteger(arr, n, h, l, r): # initialize DP dp = [-1] * h # Base condition dp[0] = 0 for i in range(n): new_dp = [-1] * h for j in range(h): if dp[j] != -1: h1 = (j + arr[i]) % h h2 = (j + arr[i] - 1) % h new_dp[h1] = max(new_dp[h1], dp[j] + (h1 >= l and h1 <= r)) new_dp[h2] = max(new_dp[h2], dp[j] + (h2 >= l and h2 <= r)) dp = new_dp ans = 0 # Compute maximum answer from all # possible cases for i in range(h): ans = max(ans, dp[i]) # Printing maximum good occurrence of X print(ans)# Driver Codeif __name__ == "__main__": A = [16, 17, 14, 20, 20, 11, 22] H = 24 L = 21 R = 23 size = len(A) goodInteger(A, size, H, L, R) |
C#
// C# codeusing System;using System.Collections.Generic;using System.Linq;public class GFG{ // Function that prints the number // of times X gets a value // between L and R static void goodInteger(int[] arr, int n, int h, int l, int r) { // initialize DP List<int> dp = new List<int>(Enumerable.Repeat(-1, h)); // Base condition dp[0] = 0; for (int i = 0; i < n; i++) { List<int> new_dp = new List<int>( Enumerable.Repeat(-1, h)); for (int j = 0; j < h; j++) { if (dp[j] != -1) { int h1 = (j + arr[i]) % h; int h2 = (j + arr[i] - 1) % h; new_dp[h1] = Math.Max(new_dp[h1], dp[j] + (h1 >= l && h1 <= r ? 1 : 0)); new_dp[h2] = Math.Max(new_dp[h2], dp[j] + (h2 >= l && h2 <= r ? 1 : 0)); } } dp = new_dp; } int ans = 0; // Compute maximum answer from all // possible cases for (int i = 0; i < h; i++) { ans = Math.Max(ans, dp[i]); } // Printing maximum good occurrence of X Console.WriteLine(ans); } // Driver Code public static void Main(string[] args) { int[] A = { 16, 17, 14, 20, 20, 11, 22 }; int H = 24; int L = 21; int R = 23; int size = A.Length; goodInteger(A, size, H, L, R); }}// This code is contributed by Utkarsh |
Javascript
// Javascript implementation of the// above approach// Function that prints the number// of times X gets a value// between L and Rfunction goodInteger(arr, n, h, l, r) {// Initialize DPconst dp = new Array(h).fill(-1);// Base conditiondp[0] = 0;for (let i = 0; i < n; i++) { const new_dp = new Array(h).fill(-1); for (let j = 0; j < h; j++) { if (dp[j] !== -1) { const h1 = (j + arr[i]) % h; const h2 = (j + arr[i] - 1) % h; new_dp[h1] = Math.max(new_dp[h1], dp[j] + (h1 >= l && h1 <= r ? 1 : 0)); new_dp[h2] = Math.max(new_dp[h2], dp[j] + (h2 >= l && h2 <= r ? 1 : 0)); } } dp.splice(0, dp.length, ...new_dp);}let ans = 0;// Compute maximum answer from all // possible casesfor (let i = 0; i < h; i++) { ans = Math.max(ans, dp[i]);}// Printing maximum good occurrence of Xdocument.write(ans);}// Driver Codeconst A = [16, 17, 14, 20, 20, 11, 22];const H = 24;const L = 21;const R = 23;const size = A.length;goodInteger(A, size, H, L, R);// This code is contributed by Pushpesh Raj |
Output
3
Time Complexity: O(N * H)
Auxiliary Space: O(H)
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!