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].

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Data structures

Range queries

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

Solutions:
class Solution:

	def movesToChessboard(self, board):
		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
		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):
		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):
		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)
		elif 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)
		elif 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):
		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