Given an array A, we may rotate it by a non-negative integer K so that the array becomes A[K], A[K+1], A{K+2], ... A[A.length - 1], A[0], A[1], ..., A[K-1].  Afterward, any entries that are less than or equal to their index are worth 1 point. 

For example, if we have [2, 4, 1, 3, 0], and we rotate by K = 2, it becomes [1, 3, 0, 2, 4].  This is worth 3 points because 1 > 0 [no points], 3 > 1 [no points], 0 <= 2 [one point], 2 <= 3 [one point], 4 <= 4 [one point].

Over all possible rotations, return the rotation index K that corresponds to the highest score we could receive.  If there are multiple answers, return the smallest such index K.


Example 1:
Input: [2, 3, 1, 4, 0]
Output: 3
Explanation:  
Scores for each K are listed below: 
K = 0,  A = [2,3,1,4,0],    score 2
K = 1,  A = [3,1,4,0,2],    score 3
K = 2,  A = [1,4,0,2,3],    score 3
K = 3,  A = [4,0,2,3,1],    score 4
K = 4,  A = [0,2,3,1,4],    score 3


So we should choose K = 3, which has the highest score.

 


Example 2:
Input: [1, 3, 0, 2, 4]
Output: 0
Explanation:  A will always have 3 points no matter how it shifts.
So we will choose the smallest K, which is 0.


Note:


       A will have length at most 20000.
       A[i] will be in the range [0, A.length].

Difficulty: interview

Starter code:

class Solution:
    def bestRotation(self, A: List[int]) -> int:
        

Solutions:
class Solution:
     def movesToChessboard(self, board):
         """
         :type board: List[List[int]]
         :rtype: int
         """
         rows = [1]
 
         for i in range(1, len(board)):
             num = self.get_num(board[0], board[i])
             if 0 <= num <= 1:
                 rows.append(num)
             else:
                 return -1
 
         r1 = self.swap_count(rows)
         if r1 != -1:
             r2 = self.swap_count(board[0])
 
         if r1 == -1 or r2 == -1:
             return -1
         else:
             return r1 + r2
 
     def get_num(self, r1, r2):
         eq = True
         op = True
 
         for i in range(len(r1)):
             if r1[i] == r2[i]:
                 op = False
             else:
                 eq = False
 
         if eq:
             return 1
         elif op:
             return 0
         else:
             return -1
 
     def swap_count(self, bits):
         n = len(bits)
 
         ones = sum(bits)
         zeros = n - ones
 
         ones_in_even = 0
         zeros_in_even = 0
         for i in range(0, n, 2):
             ones_in_even += bits[i]
             zeros_in_even += (1 - bits[i])
 
         if abs(ones - zeros) > 1:
             return -1
 
         # get rid of smaller ones
         if n % 2 == 0:
             return min(zeros_in_even, ones_in_even)
         elif ones > zeros:
             return zeros_in_even
         else:
             return ones_in_even

class Solution:
     def movesToChessboard(self, board):
         """
         :type board: List[List[int]]
         :rtype: int
         """
         N = len(board)
         for i in range(N):
             for j in range(N):
                 if board[0][0] ^ board[0][j] ^ board[i][0] ^ board[i][j]: return -1
             
         
         rowSum = 0
         colSum = 0
         rowSwap = 0
         colSwap = 0
         for i in range(N):
             rowSum += board[0][i]
             colSum += board[i][0]
             rowSwap += board[0][i] == i%2
             colSwap += board[i][0] == i%2
         
         if rowSum < N // 2 or rowSum > (N+1) // 2: return -1
         if colSum < N // 2 or colSum > (N+1) // 2: return -1
         if N % 2:
             if rowSwap % 2: rowSwap = N - rowSwap
             if colSwap % 2: colSwap = N - colSwap
         
         else:
             rowSwap = min(rowSwap, N - rowSwap)
             colSwap = min(colSwap, N - colSwap)
         
         return (rowSwap + colSwap) // 2

class Solution:
     def movesToChessboard(self, board):
         """
         :type board: List[List[int]]
         :rtype: int
         """
         n = len(board)
         for i in range(1, n):
             for j in range(1, n):
                 if (board[0][0] + board[0][j] + board[i][0] + board[i][j]) % 2 != 0:
                     return -1
         result = 0
         x = 0
         y = 0
         for i in range(0, n):
             if i % 2 == 0 and board[i][0] == 1:
                 x += 1
             elif i % 2 == 1 and board[i][0] == 0:
                 y += 1
         if n % 2 == 0:
             if x != y:
                 return -1
             result += min(x, n // 2 - x)
         else:
             if x == y:
                 result += x
             elif (n + 1) // 2 - x == (n - 1) // 2 - y:
                 result += (n + 1) // 2 - x
             else:
                 return -1
         x = 0
         y = 0
         for i in range(0, n):
             if i % 2 == 0 and board[0][i] == 1:
                 x += 1
             elif i % 2 == 1 and board[0][i] == 0:
                 y += 1
         if n % 2 == 0:
             if x != y:
                 return -1
             result += min(x, n // 2 - x)
         else:
             if x == y:
                 result += x
             elif (n + 1) // 2 - x == (n - 1) // 2 - y:
                 result += (n + 1) // 2 - x
             else:
                 return -1
         return result



 class Solution:
     def movesToChessboard(self, board):
         N = len(board)
         R = [sum([board[i][j]<<j for j in range(N)]) for i in range(N) ]
         C = [sum([board[i][j]<<i for i in range(N)]) for j in range(N) ]
         def calcMove(R, N):
             def sumOne(n) :
                 k = 0
                 while n:
                     n = n&(n-1)
                     k+=1
                 return k
             d = {}
             for i in range(N):
                 if not R[i] in d:
                     d[R[i]] = []
                 d[R[i]].append(i)
             akey =[]
             for k in d:
                 akey.append(k)
             
             if len(akey)==2 and akey[0]^akey[1] == (1<<N) -1 and abs(sumOne(akey[0])-sumOne(akey[1]))<=1:
                 a0, a1 = d[akey[0]], d[akey[1]]
                 if abs(len(a0)-len(a1))>1:
                     return -1
                 if len(a0) >= len(a1):
                     res = sum( [i%2  for i in a0])
                 else:
                     res = sum( [i%2  for i in a1])
                 return res if N%2 else min(res, max(N//2-res, 0))
             return -1
         r, c = calcMove(R, N), calcMove(C, N)
         return -1 if r == -1 or c == -1 else r + c

class Solution:
     def movesToChessboard(self, board):
         """
         :type board: List[List[int]]
         :rtype: int
         """
         import collections 
         N=len(board)
         result=0
         for count in (collections.Counter(map(tuple,board)),collections.Counter(zip(*board))):
             if len(count)!=2 or sorted(count.values())!=[N//2,(N+1)//2]:
                 return -1
             seq1,seq2=count
             if any(x==y for x,y in zip(seq1,seq2)):
                 return -1
             begins=[int(seq1.count(1)*2>N)] if N%2 else [0,1]
             result+=min(sum(int(i%2!=v) for i,v in enumerate(seq1,begin)) for begin in begins)//2
         return result

# observation:
 #1) row swapping resolves adjacent vertical 1s and 0s.
 #   col swapping resolves adjacent horizontal 1s and 0s.
 #2) if mask = all 1s with len of n. then the rows/cols must be
 #   x, x^mask, x, x^mask, ...
 class Solution:
     def movesToChessboard(self, board):
         """
         :type board: List[List[int]]
         :rtype: int
         """
         n = len(board)
         all1s = 2**n - 1
         def countSwap(lines):
             lines = [int(l, base=2) for l in lines]
             x, y = lines.count(lines[0]), lines.count(lines[0] ^ all1s)
             if x + y < n or abs(x - y) > 1:
                 return -1
             nums = [lines[0], lines[0] ^ all1s]
             if x == y:
                 return min(sum(nums[i % 2] != lines[i] for i in range(n)), sum(nums[1 - i % 2] != lines[i] for i in range(n))) // 2
             else:
                 if x < y:
                     nums = [lines[0] ^ all1s, lines[0]]
                 return sum(nums[i % 2] != lines[i] for i in range(n)) // 2
         
         cnt1 = countSwap([''.join(map(str, r)) for r in board])
         cnt2 = countSwap([''.join(str(board[i][j]) for i in range(n)) for j in range(n)])
         if cnt1 < 0 or cnt2 < 0:
             return -1
         return cnt1 + cnt2