Maximum count of values of S modulo M lying in a range [L, R] after performing given operations on the array
Given an array arr[] of N integers along with integers M, L, R. Consider a variable S(initially 0). The task is to find the maximum count of values of S % M that lies in the range [L, R] after performing the following operations for each element in the given array:
- Add arr[i] or arr[i] – 1 to S.
- Change S to S % M.
Examples:
Input: arr[] = {17, 11, 10, 8, 15}, M = 22, L = 14, R = 16
Output: 3
Explanation:
Initially S = 0,
Step 1: Choose, arr[0] – 1 = 16 and add it to S = 16 and S%M = 16. Therefore, count = 1
Step 2: Choose, arr[1] = 11 and add it to S = 16 + 11 = 27 and S%M = 5. Therefore, count = 1
Step 3: Choose, arr[2] = 10 and add it to S = 16 + 10 +11 = 37 and S%M = 15. Therefore, count = 2
Step 4: Choose, arr[3] = 8 and add it to S = 16 + 10 + 11 + 8 = 45 and S%M = 1. Therefore, count = 2
Step 5: Choose, arr[4] = 15 and add it to S = 16 + 10 + 11 + 8 + 15 = 60 and S%M = 16. Therefore, count = 3.
Hence the maximum count is 3.Input: arr[] = {23, 1}, M = 24, L = 21, R = 23
Output: 2
Naive Approach: The simplest approach is to traverse the given array arr[] and add arr[i] or arr[i – 1] to the given S and check if S%M lies in the range [L, R] or not. Since there are two possibilities to choose the given numbers. Therefore, use recursion to recursively get the maximum count of values of S%M lies in the range [L, R].
Time Complexity: O(2N)
Auxiliary Space: O(N)
Efficient Approach: To optimize the above approach the idea is to use Dynamic Programming to store the overlapping subproblems and then find the maximum count of S%M lies in the range [L, R]. Follow the steps below to solve the problem:
- Initialize a unordered_map dp to store the values of states that have overlapping subproblems.
- Initialize the sum to be 0, and then recursively add arr[i] or arr[i] – 1 value to the sum S.
- At every step, check whether the S%M lies in the range [L, R] or not. If it lies in the range then count that value and update this current state in the above map dp as 1. Else update as 0.
- After looking out for all possible combinations, return the count of values of S%M that lies in the range [L, R].
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Lookup table map<pair< int , int >, int > dp; // Function to count the value of S // after adding arr[i] or arr[i - 1] // to the sum S at each time int countMagicNumbers( int idx, int sum, int a[], int n, int m, int l, int r) { // Base Case if (idx == n) { // Store the mod value int temp = sum % m; // If the mod value lies in // the range then return 1 if (temp == l || temp == r || (temp > l && temp < r)) return dp[{ idx, sum }] = 1; // Else return 0 else return dp[{ idx, sum }] = 0; } // Store the current state pair< int , int > curr = make_pair(idx, sum); // If already computed, return the // computed value if (dp.find(curr) != dp.end()) return dp[curr]; // Recursively adding the elements // to the sum adding ai value int ls = countMagicNumbers(idx + 1, sum + a[idx], a, n, m, l, r); // Adding arr[i] - 1 value int rs = countMagicNumbers(idx + 1, sum + (a[idx] - 1), a, n, m, l, r); // Return the maximum count to // check for root value as well int temp1 = max(ls, rs); int temp = sum % m; // Avoid counting idx = 0 as possible // solution we are using idx != 0 if ((temp == l || temp == r || (temp > l && temp < r)) && idx != 0) { temp1 += 1; } // Return the value of current state return dp[{ idx, sum }] = temp1; } // Driver Code int main() { int N = 5, M = 22, L = 14, R = 16; int arr[] = { 17, 11, 10, 8, 15 }; cout << countMagicNumbers(0, 0, arr, N, M, L, R); return 0; } |
Java
// Java program for the above approach import java.util.*; import java.awt.Point; public class Main { // Lookup table static HashMap<Point, Integer> dp = new HashMap<Point, Integer>(); // Function to count the value of S // after adding arr[i] or arr[i - 1] // to the sum S at each time static int countMagicNumbers( int idx, int sum, int [] a, int n, int m, int l, int r) { // Base Case if (idx == n) { // Store the mod value int Temp = sum % m; // If the mod value lies in // the range then return 1 if (Temp == l || Temp == r || (Temp > l && Temp < r)) { dp.put( new Point(idx, sum), 1 ); return dp.get( new Point(idx, sum)); } // Else return 0 else { dp.put( new Point(idx, sum), 0 ); return dp.get( new Point(idx, sum)); } } // Store the current state Point curr = new Point(idx, sum); // If already computed, return the // computed value if (dp.containsKey(curr)) return dp.get(curr); // Recursively adding the elements // to the sum adding ai value int ls = countMagicNumbers(idx + 1 , sum + a[idx], a, n, m, l, r); // Adding arr[i] - 1 value int rs = countMagicNumbers(idx + 1 , sum + (a[idx] - 1 ), a, n, m, l, r); // Return the maximum count to // check for root value as well int temp1 = Math.max(ls, rs); int temp = sum % m; // Avoid counting idx = 0 as possible // solution we are using idx != 0 if ((temp == l || temp == r || (temp > l && temp < r)) && idx != 0 ) { temp1 += 1 ; } // Return the value of current state dp.put( new Point(idx, sum), temp1); return dp.get( new Point(idx, sum)); } public static void main(String[] args) { int N = 5 , M = 22 , L = 14 , R = 16 ; int [] arr = { 17 , 11 , 10 , 8 , 15 }; System.out.print(countMagicNumbers( 0 , 0 , arr, N, M, L, R)); } } // This code is contributed by divyesh072019. |
Python3
# Python3 program for the above approach # Lookup table dp = {} # Function to count the value of S # after adding arr[i] or arr[i - 1] # to the sum S at each time def countMagicNumbers(idx, sum , a, n, m, l, r): # Base Case if (idx = = n): # Store the mod value temp = sum % m # If the mod value lies in # the range then return 1 if (temp = = l or temp = = r or (temp > l and temp < r)): dp[(idx, sum )] = 1 return dp[(idx, sum )] # Else return 0 else : dp[(idx, sum )] = 0 return dp[(idx, sum )] # Store the current state curr = (idx, sum ) # If already computed, return the # computed value if (curr in dp): return dp[curr] # Recursively adding the elements # to the sum adding ai value ls = countMagicNumbers(idx + 1 , sum + a[idx], a, n, m, l, r) # Adding arr[i] - 1 value rs = countMagicNumbers(idx + 1 , sum + (a[idx] - 1 ), a, n, m, l, r) # Return the maximum count to # check for root value as well temp1 = max (ls, rs) temp = sum % m # Avoid counting idx = 0 as possible # solution we are using idx != 0 if ((temp = = l or temp = = r or (temp > l and temp < r)) and idx ! = 0 ): temp1 + = 1 # Return the value of current state dp[(idx, sum )] = temp1 return dp[(idx, sum )] # Driver Code if __name__ = = '__main__' : N = 5 M = 22 L = 14 R = 16 arr = [ 17 , 11 , 10 , 8 , 15 ] print (countMagicNumbers( 0 , 0 , arr, N, M, L, R)) # This code is contributed by mohit kumar 29 |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG { // Lookup table static Dictionary<Tuple< int , int >, int > dp = new Dictionary<Tuple< int , int >, int >(); // Function to count the value of S // after adding arr[i] or arr[i - 1] // to the sum S at each time static int countMagicNumbers( int idx, int sum, int [] a, int n, int m, int l, int r) { // Base Case if (idx == n) { // Store the mod value int Temp = sum % m; // If the mod value lies in // the range then return 1 if (Temp == l || Temp == r || (Temp > l && Temp < r)) return dp[ new Tuple< int , int >(idx, sum)] = 1; // Else return 0 else return dp[ new Tuple< int , int >(idx, sum)] = 0; } // Store the current state Tuple< int , int > curr = new Tuple< int , int >(idx, sum); // If already computed, return the // computed value if (dp.ContainsKey(curr)) return dp[curr]; // Recursively adding the elements // to the sum adding ai value int ls = countMagicNumbers(idx + 1, sum + a[idx], a, n, m, l, r); // Adding arr[i] - 1 value int rs = countMagicNumbers(idx + 1, sum + (a[idx] - 1), a, n, m, l, r); // Return the maximum count to // check for root value as well int temp1 = Math.Max(ls, rs); int temp = sum % m; // Avoid counting idx = 0 as possible // solution we are using idx != 0 if ((temp == l || temp == r || (temp > l && temp < r)) && idx != 0) { temp1 += 1; } // Return the value of current state return dp[ new Tuple< int , int >(idx, sum)] = temp1; } static void Main() { int N = 5, M = 22, L = 14, R = 16; int [] arr = { 17, 11, 10, 8, 15 }; Console.Write(countMagicNumbers(0, 0, arr, N, M, L, R)); } } // This code is contributed by divyeshrabadiya07. |
Javascript
<script> // Javascript program for the above approach // Lookup table let dp = new Map(); // Function to count the value of S // after adding arr[i] or arr[i - 1] // to the sum S at each time function countMagicNumbers(idx, sum, a, n, m, l, r) { // Base Case if (idx == n) { // Store the mod value let temp = sum % m; // If the mod value lies in // the range then return 1 if (temp == l || temp == r || (temp > l && temp < r)) return dp[[ idx, sum ]] = 1; // Else return 0 else return dp[[ idx, sum ]] = 0; } // Store the current state let curr = [idx, sum]; // If already computed, return the // computed value if (dp.has(curr)) return dp[curr]; // Recursively adding the elements // to the sum adding ai value let ls = countMagicNumbers(idx + 1, sum + a[idx], a, n, m, l, r); // Adding arr[i] - 1 value let rs = countMagicNumbers(idx + 1, sum + (a[idx] - 1), a, n, m, l, r); // Return the maximum count to // check for root value as well let temp1 = Math.max(ls, rs); let temp = sum % m; // Avoid counting idx = 0 as possible // solution we are using idx != 0 if ((temp == l || temp == r || (temp > l && temp < r)) && idx != 0) { temp1 += 1; } // Return the value of current state dp[[ idx, sum ]] = temp1; return dp[[ idx, sum ]]; } let N = 5, M = 22, L = 14, R = 16; let arr = [ 17, 11, 10, 8, 15 ]; document.write(countMagicNumbers(0, 0, arr, N, M, L, R)); // This code is contributed by mukesh07. </script> |
3
Time Complexity: O(S*N), where N is the size of the given array, and S is the sum of all array elements.
Space Complexity: O(S*N)
Contact Us