Question

2
task3
There are N coins, each showing either heads or tails. We would like all the
coins to form a sequence of alternating heads and tails. What is the
minimum number of coins that must be reversed to achieve this?
3
solution.java
test-input.txt
Write a function:
class Solution { public int solution(int[] A); }
that, given an array A consisting of N integers representing the coins, returns
the minimum number of coins that must be reversed. Consecutive elements
bf array A represent consecutive coins and contain either a 0 (heads) or a 1
(tails).
Examples:
11. Given array A = [1,0,1,0, 1, 1), the function should return 1. After reversing
the sixth coin, we achieve an alternating sequence of coins (1,0,1,0, 1, 0).
Test Output
k. Given array A = [1,1,0, 1, 1), the function should return 2. After reversing
the first and fifth coins, we achieve an alternating sequence (0, 1, 0, 1, 0).
3. Given array A = [0, 1, 0], the function should return 0. The sequence of
coins is already alternating.
4. Given array A = [0, 1, 1, 0], the function should return 2. We can reverse the
first and second coins to get the sequence: (1, 0, 1, 0).
Assume that:
?
• N is an integer within the range (1..100);
each element of array A is an integer that can have one of the​

Answer 1

Answer:

Given array A = [1,0,1,0, 1, 1), the function should return 1. After reversing

the sixth coin, we achieve an alternating sequence of coins (1,0,1,0, 1, 0).

Test Output

Answer 2

Answer:

def solution(A):

 n = len(A)

 dp = [[0 for x in range(2)] for y in range(n)]

 if A[n-1] == 0:

   dp[n-1][0] = 0

   dp[n-1][1] = 1

 else:

   dp[n-1][0] = 1

   dp[n-1][1] = 0

 

 for i in reversed(range(len(A)-1)):

   if A[0] == 0:

     dp[i][0] = dp[i+1][1]

     dp[i][1] = dp[i+1][0] + 1

   else:

     dp[i][0] = dp[i+1][1] + 1

     dp[i][1] = dp[i+1][0]

 return min(dp[0][0], dp[0][1])

Explanation: