javabinaryflipalternating

Minimum alternating binary series count (coin flip problem)


Given N coins in a row, I need to count the minimum changes necessary to make the series perfectly alternating. For example, [1, 1, 0, 1, 1] must become [0, 1, 0, 1, 0] which requires only 2 changes. Note that [1, 0, 1, 0, 1] is incorrect, as it requires 3 changes. I have a mostly function program here:

public int solution(int[] num) {
    int[] sequence = num;//Make a copy of the incoming array so I can change values
    int flips = 0;//Store values here
    boolean changeNeeded = false;//How to know if a flip must occur
    for (int i = 1; i < sequence.length; i++) {//Count entire array, starting with index 1 so the pprevious entry can be checked for diplicity
        if (sequence[i] == sequence[i - 1]) {//checking previous entry
            flips++;//increment neccessary flip
            changeNeeded = true;//Make sure to change the value so it doesn't get incremented twice
        }
        if (sequence[i] == 1 && changeNeeded) {//Change a 1 to a 0
        sequence[i] = 0; 
        changeNeeded = false;
        } else if (sequence[i] == 0 && changeNeeded) {//change a 0 to a 1
        sequence[i] = 1;
        changeNeeded = false;
        }
    }
    return flips;//done
}

However, because it starts counting at index = 1 it cannot solve the above problem correctly. I am yet to find a way to both count the end bound and stay within bounds.

SOLUTION: I managed to adjust my code until it worked properly, though it's one of those "I don't know why, but this works" answers. The answer I tagged is far superior.

boolean changeNeeded = false; //Just as the name says, it checks for when an integer change if it is necessary
    int flips = 0;
    int[] sequence = num; //So I can copy and edit the incoming array if needed
    for (int i = 0; i < num.length; i++) {
        sequence[i] = A[i];//Copy all elements
    }
    for (int i = 0; i < sequence.length - 1; i++) { //Count the array, capping our count so we avoid indexOutOfBounds errors
        
        if (sequence[i] == sequence[i + 1]) //Compare current to next entry
        {
            flips++;//increment a fix
            changeNeeded = true;//tell the system that a digit needs changed
        }
        if (sequence[i] == 1 && changeNeeded) //change a 1 to a 0
        {
            sequence[i] = 0;
            changeNeeded = false; //reset our change detection
        }
        else if (sequence[i] == 0 && changeNeeded) //change a 0 to a 1
        {
            sequence[i] = 1;
            changeNeeded = false; //see above
        }
    }
    if (sequence[0] == sequence[1]) {//The above system skips properly adjusting the 0th index, so it needs to be checked after
        flips++;
        //If checked within the loop it will add an extra, unnecessary flip. I don't know why.
    }
    return flips;

Solution

  • No need to modify the original array at all.

    IIUC there are two options: you need to change your sequence to 1010... or 0101... You should count how many changes are needed for both and return min?

    So for each even index, you increment changesWithLeading0 if the value is not 0. For each odd index, you increment changesWithLeading0 if the value is not 1.

    For changesWithLeading1 you do the opposite.

    public int solution(int[] num) {
      int changesWithLeading0 = 0;
      int changesWithLeading1 = 0;
      for int(i = 0; i < sequence.length; i++) {
        if (sequence[i] == 1 - (i % 2)) {
          changesWithLeading0 ++;
        }
        if (sequence[i] == i % 2) {
          changesWithLeading1 ++;
        }
      }
      return Math.min(changesWithLeading0, changesWithLeading1);
    }