Maximum count of values of S modulo M lying in a range [ L , R ] after performing given operations on the array | Java 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
import java . util . * ; import java . awt . Point ; public class Main { static HashMap < Point , Integer > dp = new HashMap < Point , Integer > ( ) ; static 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 ) ) { dp . put ( new Point ( idx , sum ) , 1 ) ; return dp . get ( new Point ( idx , sum ) ) ; } else { dp . put ( new Point ( idx , sum ) , 0 ) ; return dp . get ( new Point ( idx , sum ) ) ; } } Point curr = new Point ( idx , sum ) ; if ( dp . containsKey ( curr ) ) return dp . get ( 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 = Math . max ( ls , rs ) ; int temp = sum % m ; if ( ( temp == l || temp == r || ( temp > l && temp < r ) ) && idx != 0 ) { temp1 += 1 ; } 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 ) ) ; } }