Minimize count of flips required to make sum of the given array equal to 0 | Initialize dp [ ] [ ] ; Function to find the minimum number of operations to make sum of A [ ] 0 ; Initialize answer ; Base case ; Otherwise , return 0 ; Pre - computed subproblem ; Recurrence relation for finding the minimum of the sum of subsets ; Return the result ; Function to find the minimum number of elements required to be flipped to amke sum the array equal to 0 ; Find the sum of array ; Initialise dp [ ] [ ] with - 1 ; No solution exists ; Otherwise ; If sum is odd , no subset is possible ; Driver Code ; Function Call
dp = [ [ - 1 for i in range ( 2001 ) ] for j in range ( 2001 ) ] NEW_LINE def solve ( A , i , sum , N ) : NEW_LINE INDENT res = 2001 NEW_LINE if ( sum < 0 or ( i == N and sum != 0 ) ) : NEW_LINE INDENT return 2001 NEW_LINE DEDENT if ( sum == 0 or i >= N ) : NEW_LINE INDENT dp [ i ] [ sum ] = 0 NEW_LINE return 0 NEW_LINE DEDENT if ( dp [ i ] [ sum ] != - 1 ) : NEW_LINE INDENT return dp [ i ] [ sum ] NEW_LINE DEDENT res = min ( solve ( A , i + 1 , sum - A [ i ] , N ) + 1 , solve ( A , i + 1 , sum , N ) ) NEW_LINE dp [ i ] [ sum ] = res NEW_LINE return res NEW_LINE DEDENT def minOp ( A , N ) : NEW_LINE INDENT sum = 0 NEW_LINE for it in A : NEW_LINE INDENT sum += it NEW_LINE DEDENT if ( sum % 2 == 0 ) : NEW_LINE INDENT dp = [ [ - 1 for i in range ( 2001 ) ] for j in range ( 2001 ) ] NEW_LINE ans = solve ( A , 0 , sum // 2 , N ) NEW_LINE if ( ans < 0 or ans > N ) : NEW_LINE INDENT print ( " - 1" ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( ans ) NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT print ( - 1 ) NEW_LINE DEDENT DEDENT A = [ 2 , 3 , 1 , 4 ] NEW_LINE N = len ( A ) NEW_LINE minOp ( A , N ) NEW_LINE