This question was asked in CodeChef Starters 10 Division 2 (Rated), I solved this question using recursion ( which failed because it got TLE).
I tried my best to convert it into DP but wasn’t able to do it.
Question Name: Magical Flips (CRDFLP)
Question Link: https://www.codechef.com/START10B/problems/CRDFLP
def solve(idx, prev_and, flips): global max_and global min_flips if idx == n: if prev_and > max_and: max_and = prev_and min_flips = flips return solve(idx+1, prev_and&arr[idx], flips) solve(idx+1, prev_and&brr[idx], flips+1) for _ in range(int(input())): n = int(input()) arr = list(map(int, input().split())) brr = list(map(int, input().split())) max_and = -1 min_flips = 0 d = dict() solve(0, 2**31-1, 0) print(max_and, min_flips)
My Logic: My logic was simple, for each card we have 2 options either we take the front face card number in our final result or we take the back face number, and then we have to calculate the maximum and from all available combinations.
My code is currently O(2^n) but by using DP it can be reduced.
Only suggestions will also be helpful ( or code in any language )
Thanks in advance.