Maximum count of values of S modulo M lying in a range [ L , R ] after performing given operations on the array | 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
dp = { } NEW_LINE def countMagicNumbers ( idx , sum , a , n , m , l , r ) : NEW_LINE INDENT if ( idx == n ) : NEW_LINE INDENT temp = sum % m NEW_LINE if ( temp == l or temp == r or ( temp > l and temp < r ) ) : NEW_LINE INDENT dp [ ( idx , sum ) ] = 1 NEW_LINE return dp [ ( idx , sum ) ] NEW_LINE DEDENT else : NEW_LINE INDENT dp [ ( idx , sum ) ] = 0 NEW_LINE return dp [ ( idx , sum ) ] NEW_LINE DEDENT DEDENT curr = ( idx , sum ) NEW_LINE if ( curr in dp ) : NEW_LINE INDENT return dp [ curr ] NEW_LINE DEDENT ls = countMagicNumbers ( idx + 1 , sum + a [ idx ] , a , n , m , l , r ) NEW_LINE rs = countMagicNumbers ( idx + 1 , sum + ( a [ idx ] - 1 ) , a , n , m , l , r ) NEW_LINE temp1 = max ( ls , rs ) NEW_LINE temp = sum % m NEW_LINE if ( ( temp == l or temp == r or ( temp > l and temp < r ) ) and idx != 0 ) : NEW_LINE INDENT temp1 += 1 NEW_LINE DEDENT dp [ ( idx , sum ) ] = temp1 NEW_LINE return dp [ ( idx , sum ) ] NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 5 NEW_LINE M = 22 NEW_LINE L = 14 NEW_LINE R = 16 NEW_LINE arr = [ 17 , 11 , 10 , 8 , 15 ] NEW_LINE print ( countMagicNumbers ( 0 , 0 , arr , N , M , L , R ) ) NEW_LINE DEDENT