Maximum count of values of S modulo M lying in a range [ L , R ] after performing given operations on the array | C ++ program for the above approach ; Lookup table ; Function to count the value of S after adding arr [ i ] or arr [ i - 1 ] to the sum S at each time ; Base Case ; Store the mod value ; If the mod value lies in the range then return 1 ; Else return 0 ; Store the current state ; If already computed , return the computed value ; Recursively adding the elements to the sum adding ai value ; Adding arr [ i ] - 1 value ; Return the maximum count to check for root value as well ; Avoid counting idx = 0 as possible solution we are using idx != 0 ; Return the value of current state ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; map < pair < int , int > , int > dp ; int countMagicNumbers ( int idx , int sum , int a [ ] , int n , int m , int l , int r ) { if ( idx == n ) { int temp = sum % m ; if ( temp == l || temp == r || ( temp > l && temp < r ) ) return dp [ { idx , sum } ] = 1 ; else return dp [ { idx , sum } ] = 0 ; } pair < int , int > curr = make_pair ( idx , sum ) ; if ( dp . find ( curr ) != dp . end ( ) ) return dp [ curr ] ; int ls = countMagicNumbers ( idx + 1 , sum + a [ idx ] , a , n , m , l , r ) ; int rs = countMagicNumbers ( idx + 1 , sum + ( a [ idx ] - 1 ) , a , n , m , l , r ) ; int temp1 = max ( ls , rs ) ; int temp = sum % m ; if ( ( temp == l || temp == r || ( temp > l && temp < r ) ) && idx != 0 ) { temp1 += 1 ; } return dp [ { idx , sum } ] = temp1 ; } 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 ; }