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;
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);
}