Wrong answer in task - mistake in algorithm

Question

I doing my homework (first sorry for english).

Consider N coins aligned in a row. Each coin is showing either heads or tails. The adjacency of these coins is the number of pairs of adjacent coinst showing the same face.Return the maximum possible adjacency that can be obtained by reversing one coin, one of the coinst must be reversed

for example i have

1 1 0 1 0 0 

and after change third we get 1 1 1 1 0 0 so we have 4 pairs.

But my code doesn't work for example

1 1 

I should get 0 but get 1

  public static void main(String[] args) {
    int[] A = {1, 1};

    int n = A.length;
    int result = 0;
    for (int i = 0; i < n - 1; i++) {
        if (A[i] == A[i + 1])
            result = result + 1;
    }
    int r = 0;
    for (int i = 0; i < n; i++) {
        int count = 0;
        if (i > 0) {
            if (A[i - 1] != A[i])
                count = count + 1;
            else
                count = count - 1;
        }
        if (i < n - 1) {
            if (A[i + 1] != A[i])
                count = count + 1;
            else
                count = count - 1;
        }
        r = Math.max(r, count);
    }
    System.out.println(result + r);
}

where I made mistake?

Answer 1

I solved this question of coins reversal to get alternative heads and tails in python. Here is the solution for question with proper passed test cases.

def coins_reversal(A):
"""
Reverse the coins to get alternative heads and tails.

:param list A: list of heads and tails of coins
:return: number of coins to reverse to get alternative heads and tails
"""
   result = 0
   NEW_A = A.copy()
   for i in range(0, len(A) - 1):
       if NEW_A[i] == 0 and NEW_A[i+1] == 0:
           result += 1
           if NEW_A[i - 1] == 0:
               NEW_A[i] = 1
           else:
               NEW_A[i + 1] = 1
       elif NEW_A[i] == 1 and NEW_A[i+1] == 1:
           result += 1
           if NEW_A[i - 1] == 1:
               NEW_A[i] = 0
           else:
               NEW_A[i + 1] = 0
   return result

Answer 2

In this solution I did it in linear way

public static void main(String[] args) {
    int[] A = { 1, 1, 0, 1, 0, 0};

    int sum1 = 0, sum2 = 0;
    for (int i = 0; i < A.length; i++) {
        if (i % 2 === 0) {
            if (0 !== A[i]) {
                sum1++;
            }
            if (1 !== A[i]) {
                sum2++;
            }
        } else {
            if (1 !== A[i]) {
                sum1++;
            }
            if (0 !== A[i]) {
                sum2++;
            }
        }
    }
    if (sum1 > sum2) {
        System.out.println(sum2);
    }
    else {
        System.out.println(sum1);
    }
}

Answer 3

There are 2 mistakes that I found; The first one related if all elements in the array are the same.

[1,1,1,1,1]

The second one if our array have exactly one element.

[1]

Code:

public static int solution(int[] A) 
{
            int n = A.length;
            int result = 0; 

            for (int i = 0; i < n - 1; ) 
            {
                if (A[i] == A[i + 1]) 
                    result = result + 1;
                i = i+1;
            }
            // Add these 2 lines below

            if (A.length == 1 )  return 0; 
            if (result == n-1)   return result-1;

            int max = 0;
            for (int i = 0; i <n; i++) 
            {
                int count = 0;
                if (i > 0)   
                {
                    if (A[i-1] != A[i])
                        count = count + 1;    
                    else
                       count = count - 1;
                }
                if (i < n - 1) 
                {
                    if (A[i] != A[i + 1])   // starting with 0
                        count = count + 1;
                    else
                        count = count - 1;
                }               
                max = Math.max(max,count);              
            }     
            return result + max; // 
        }

Answer 4

I agree with one of the answers here saying that you have to pay attention to the rule: "one of the coins must be reversed" which means that you must flip one coin.

And there's also a rule saying that you are not allowed to add or remove lines of code, and that you can only modify at most three lines of code, right?

The problem is when the coins are initially all on the same face. Let's say we have this test case:

0 0 0 0 0 0

the initial state is 5 pairs, but after flipping exactly one coin, the highest possible number of pairs should be 4 (while the original code returns 5).

So, my decision for this problem is to change the initial value of the variable max to -1.

Here is the resulting code where we just need to modify exactly one line of code:

public static void main(String[] args) {
    int[] A = {1, 1};

    int n = A.length;
    int result = 0;
    for (int i = 0; i < n - 1; i++) {
        if (A[i] == A[i + 1])
            result = result + 1;
    }
    int r = -1;
    for (int i = 0; i < n; i++) {
        int count = 0;
        if (i > 0) {
            if (A[i - 1] != A[i])
                count = count + 1;
            else
                count = count - 1;
        }
        if (i < n - 1) {
            if (A[i + 1] != A[i])
                count = count + 1;
            else
                count = count - 1;
        }
        r = Math.max(r, count);
    }
    System.out.println(result + r);
}

Answer 5

public static int coinReversal(int a[]){
        int cost1 = 1, cost2 = 0;
        int b[] = a.clone();
        b[0] = 0;
        if(b[0] == 0){
            for(int i = 0 ; i < b.length-1 ; i++ ){
                if(b[i] == b[i+1] ){
                    cost1+=1;
                    if(b[i+1] == 1){
                        b[i+1] = 0;
                    }else{
                        b[i+1] = 1;
                    }
                }
            }
        }
        if(a[0] == 1){
            for(int i = 0 ; i < a.length-1 ; i++ ){
                if(a[i] == a[i+1] ){
                    cost2+=1;
                    if(a[i+1] == 1){
                        a[i+1] = 0;
                    }else{
                        a[i+1] = 1;
                    }
                }
            }
        }

        return  cost2 > cost1 ? cost1 : cost2;
    }

Answer 6

please pay attention to the "one of the coins must be reversed"

it means that you MUST flip and only ONE coin!!!

Let's analize:

1. the test case A = {1,1} or A ={0,0},
   then result =1, so after "reversing ONE coin" the result shall be changed to 0.

2. the test case A = {1,1,1} or A ={0,0,0} (all coins are facing up OR down),
   then result would be 2, so after "reversing ONE coin" the result shall be changed to 1 (taken max).

3. Etc..

Thus if (result == n-1) return result-1; must be placed in your program. Without such statement, your program is defective.

public static int solution(int[] A) 
{
            int n = A.length;
            int result = 0; 

            for (int i = 0; i < n - 1; ) 
            {
                if (A[i] == A[i + 1]) 
                    result = result + 1;
                i = i+1;
            }      
            if (result == n-1)   return result-1;   // to cover {1,1}, {1,1,1}

            int max = 0;
            for (int i = 0; i <n; i++) 
            {
                int count = 0;
                if (i > 0)   // starting up from 1 and  covering the last
                {
                    if (A[i-1] != A[i])
                        count = count + 1;    
                    else
                       count = count - 1;
                }
                if (i < n - 1) 
                {
                    if (A[i] != A[i + 1])   // starting with 0
                        count = count + 1;
                    else
                        count = count - 1;
                }               
                max = Math.max(max,count);              
            }     
            return result + max; // 
        }

Answer 7

You can achieve this by splitting the work :

• Iterate over the array, and change one by one a coin
• for each change, compute how many pairs you can make (method nbPair)

---

public static void main(String[] args) {
    int[] A = {1, 1, 0, 1, 0, 0};

    int nbPairMax = 0;
    for (int i = 0; i < A.length; i++) {
        int[] copy = Arrays.copyOf(A, A.length);
        copy[i] = (copy[i] + 1) % 2; // 0->1, 1->0
        nbPairMax = Math.max(nbPairMax, nbPair(copy));
    }
    System.out.println(nbPairMax);

}

private static int nbPair(int[] array) {
    int result = 0;
    for (int i = 0; i < array.length - 1; i++) {
        if (array[i] == array[i + 1]) {
            result = result + 1;
        }
    }
    return result;
}

---

Example, with {1, 1, 0, 1, 0, 0}, the loop will call the method nbPair() with the 6 different possible changes, and compute the number of pair you can make :

[0, 1, 0, 1, 0, 0] >> 1
[1, 0, 0, 1, 0, 0] >> 2
[1, 1, 1, 1, 0, 0] >> 4
[1, 1, 0, 0, 0, 0] >> 4
[1, 1, 0, 1, 1, 0] >> 2
[1, 1, 0, 1, 0, 1] >> 1