Given a n*m chess board. We can choose any rectangle formed by board squares and perform an inversion. Every white cell in the inverted rectangle becomes black and every black one becomes white. In the initial state the board is colored in chess style, namely every cell is either black or white and every two cells that share a side have different colors. Print the minimum inversion count.
Examples:
Input : 2 2 Output : 2 Input : 1 1 Output : 0
RECOMMENDED: Find the Minimum element in a Sorted and Rotated Array
Approach:
If the given chess board is 1*1 the answer is 0. If n=1 and m !=1.
Then answer is floor(m/2) If n!=1 and m=1 then answer is floor(n/2) If n and m both are odd then answer is ceil(n/2)+floor(m/2) If n is even and m is odd then answer is n/2+floor(m/2) If n is odd and m is even then answer is floor(n/2)+m/2
Below is the Python Implementation of the above approach.
# Function to find the minimum number of color inversion
import math as ma
def inver(n, m):
# Checking if n and m both are 1
if(n == 1 or m == 1):
return n//2 + m//2
else:
# If either of n or m is even answer is n / 2 + m / 2
if(n % 2 == 0):
return n//2 + m//2
elif(m % 2 == 0):
return n//2 + m//2
else:
# else answer is n / 2 + m / 2 + 1
return n//2 + m//2 + 1
n, m = 2, 2
print(inver(n, m))
Output:
2
Time Complexity: O(1)
Space Complexity: O(1)
Please write comments below if you find anything incorrect, or you want to share more information about the topic discussed above. A gentle request to share this topic on your social media profile.