Question

The Adjacent Coins Problem Published on 2017-08-30 Consider N coins aligned in a row. Each coin is showing either heads or tails. The adjacency of these coins is the number of adjacent pairs of coins with the same side facing up. Write a program that given a non-empty zero-indexed array A consisting of N integers representing the coins, returns the maximum possible adjacency that can be obtained by reversing exactly one coin (that is, one of the coins must be reversed). Consecutive elements of array A represent consecutive coins in the row. Array A contains only 0s and/or 1s:

Answer 1

Answer:

Here is the JAVA code:

public class Main{

public static int solution(int[] A) { //method that takes non-empty array A consisting of 0s and 1s

           int N = A.length; // number of 0s and 1s in array A

           int r = 0; //result of adjacency

           for (int i = 0; i < N - 1; i++;   )   { // iterates through A

               if (A[i] == A[i + 1])  //if i-th element of A is equal to (i+1)th element

                   r = r + 1;   }     //add 1 to the count of r

           if (r == N-1)   //for test cases like {1,1}

           {return r-1; }

           int max = 0; //to store maximum possible adjacency

           for (int i = 0; i <N; i++)   { //iterates through array

               int c = 0;

               if (i > 0)    { //starts from 1 and  covering the last

                   if (A[i-1] != A[i]) //checks if i-1 element of A is not equal to ith element of A

                       c = c + 1;    //adds 1 to counter variable

                   else

                      c = c - 1;   } //decrements c by 1

               if (i < N - 1)     {//starting with 0

                   if (A[i] != A[i + 1])  //checks if ith element of A is not equal to i+1th element of A

                       c = c + 1; //adds 1 to counter variable

                   else

                       c = c - 1;   }      //decrements c by 1        

               max = Math.max(max,c);   }  //finds the maximum of max and c

           return r + max;         } //returns result + maximum result

        public static void main(String[] args) {

   int[] A = {1, 1, 0, 1, 0, 0}; //sample array to test the method

   System.out.println(solution(A));} } //calls the method passing array to it

Explanation:

The program works as follows:

A[] = {1, 1, 0, 1, 0, 0}

N = A.length

N = 6

The A has the following elements:

A[0] =  1

A[1] = 1

A[2] = 0

A[3] = 1

A[4] = 0

A[5] = 0

Program iterates through array A using for loop. Loop variable i is initialized to 0

if condition if (A[i] == A[i + 1]) checks

if (A[0] == A[0 + 1])

A[0] =  1

A[0 + 1] = A[1] = 1

They both are 1 so they are equal

r = r + 1;  

Since the above if condition is true so 1 is added to the value of r Hence

r = 1

At each iteration of the loop the if condition checks whether the adjacent elements of A are equal. If true then r is incremented to 1 otherwise not.

So after all the iterations value of r = 2

if (r == N-1) evaluates to false because r=2 and N-1 = 5

So program moves to the statement:

for (int i = 0; i <N; i++)

This loop iterates through the array A

if (i > 0) condition checks if value of i is greater than 0. This evaluates to false and program control moves to statement:

if (i < N - 1) which makes if(0<5) This evaluates to true and program control moves to statement

if (A[i] != A[i + 1])  which means:

if (A[0] != A[0 + 1]) -> if (A[0] != A[1])

We know that

A[0] =  1

A[1] = 1

So this evaluates to false and else part is executed:

value of c is decremented to 1. So c=-1

max = Math.max(max,c) statement returns the max of max and c

max = 0

c = -1

So max = 0

value of i is incremented to 1 so i = 1

At next step:

if (i < N - 1) which makes if(1<5) This evaluates to true and program control moves to statement

if (A[i] != A[i + 1]) which means:

if (A[1] != A[1 + 1]) -> if (A[1] != A[2])

A[1] = 1

A[2] = 0

So the statement evaluates to true and following statement is executed

c = c + 1; The value of c is incremented to 1. So

c = -1 + 1

Hence

Hence c= 0, max = 0 and i = 2

next step:

if (i < N - 1) which makes if(2<5) This evaluates to true and program control moves to statement

if (A[i] != A[i + 1]) which means:

if (A[2] != A[2 + 1]) -> if (A[2] != A[3])

A[2] = 0

A[3] = 1

So the statement evaluates to true and following statement is executed

c = c + 1; The value of c is incremented to 1. So

c = 0 + 1

c = 1

Hence

The statement max = Math.max(max,c) returns the max of max and c

max = 0

c = 1

So max = 1

Hence  c= 1, max = 1 and i = 3

next step:

if (i < N - 1) which makes if(3<5) This evaluates to true and program control moves to statement

if (A[i] != A[i + 1]) which means:

if (A[3] != A[3 + 1]) -> if (A[3] != A[4])

A[3] = 1

A[4] = 0

So the statement evaluates to true and following statement is executed

c = c + 1; The value of c is incremented to 1. So

c = 1 + 1

c = 2

Hence

The statement max = Math.max(max,c) returns the max of max and c

max = 1

c = 2

So max = 2

Hence c= 2, max = 2 i = 4

next step:

if (i < N - 1) which makes if(4<5) This evaluates to true and program control moves to statement

if (A[i] != A[i + 1])  which means:

if (A[4] != A[4+ 1]) -> if (A[4] != A[5])

A[4] = 0

A[5] = 0

So this evaluates to false and else part is executed:

value of c is decremented to 1. So c=1

max = Math.max(max,c) statement returns the max of max and c

max = 2

c = 1

So max = 2

value of i is incremented to 1 so i = 5

next step:

if (i < N - 1) which makes if(5<5) This evaluates to false

if (i > 0) evaluates to true so following statement executes:

if (A[i-1] != A[i])

if (A[5-1] != A[5])

if (A[4] != A[5])

A[4] = 0

A[5] = 0

This statement evaluates to false so else part executes and value of c is decremented to 1

Hence

max = 2

c = 0

So max = 2

value of i is incremented to 1 so i = 6

The loop breaks because i <N evaluates to false.

Program control moves to the statement:

return r + max;

r = 2

max = 2

r + max = 2+2 = 4

So the output of the above program is:

4