Maximize occurrences of values between L and R on sequential addition of Array elements with modulo H
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 R void 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 Code int 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 approach 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) { 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 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 29AjayKumar |
Python3
# Python3 implementation of the above approach # Function that prints the number # of times X gets a value # between L and R def 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 Code if __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 R function 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 Code let 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> |
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 R void 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 Code int 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 R def 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 Code if __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# code using 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 R function goodInteger(arr, n, h, l, r) { // Initialize DP const dp = new Array(h).fill(-1); // Base condition dp[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 cases for (let i = 0; i < h; i++) { ans = Math.max(ans, dp[i]); } // Printing maximum good occurrence of X document.write(ans); } // Driver Code const 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 |
3
Time Complexity: O(N * H)
Auxiliary Space: O(H)
Contact Us