CODEWITHSUNDEEP
javabinarymaxsequencealternating
Reach4God
Reach4God

Reputation: 33

Java MAXIMUM outcomes, while maintaining minimum changes in an alternating binary sequence (coin flip) question

I am having an issue with a fairly common practice problem about identifying duplicates in a binary sequence (commonly called a 'coin flip' problem) and seem to gave difficulty explaining it, so bear with me. I need the minimum number of changes in an alternating binary sequence while returning the maximum different outputs this may result in.

Example: Given an array A = [1, 0, 1, 0, 1, 1] there is one minimum change that can be made to make the sequence alternating, making it A = [1, 0, 1, 0, 1, 0], so changes = 1. There are no other ways to make 1 change and keep an alternating sequence.

My problem is that I must find the number of outcomes that CAN be made. So, given array A = [0, 1, 1, 0] there are two maximum outcomes that can be made. Either [1, 0, 1, 0] or [0, 1, 0, 1], both only require changes = 2. This is likely just me not able to figure out the proper logic, see my code below:

public class Solution {
    public int Solution(int[] S) {
        int changes = 0;
        for (int i = 0; i < S.length - 1; i++) { //using length - 1 so my if statement doesn't go out of bounds
            if (S[i] == S[i + 1]) {//How I'm detecting if a duplication has occured (and why length - 1 is necessary)
                changes++;
            }
            if ((S.length >= 4 && i >= 1) && (S[i - 1] == S[i + 2] && S[i] == S[i + 1])) {//This is where I'm having logic issues. It really only addresses the specific instance listed above
                changes++;
            }
        }
        return changes;
    }
}

This works fine when finding the minimum number of possible changes, but not the outcomes. This is likely just a logic issue that I am having trouble thinking through. I've seen others asking about essentially the same question, but never trying to find this mythical 'max outcome'. If that solution exists in a different thread please send it to me. Much thanks!

*As it seems I've done a poor example of explaining what I mean by maximum outcomes I've made a better example:

With array A = [1, 1, 1, 1, 1, 1] you should return 3, resulting in [1, 0, 1, 0, 1, 0] for changing values 1, 3, and 5. this is the same number of changes as ending with [0, 1, 0, 1, 0, 1]. You need to change at least 3 values minimum to make an alternating sequence, but there is a second outcome possible with only three changes.

Upvotes: 0

Views: 127

Answers (1)

user15793316
user15793316

Reputation:

There are only two possible alternating sequences for a given number of coins: one starting with 0, the other with 1.
Assuming that a coin can only be flipped once1, there are only two possible set of changes that can be made. One resulting in the first sequence, another resulting in the second solution. both set of changes are complementary, so the sum of changes of both must be the number of coins.

Example 3 coins

Possible sequences:

  • 0, 1, 0
  • 1, 0, 1

Starting with 0, 1, 1, we can flip:

  • the 3rd coin and get first sequence
  • flip the 1st and 2nd coins to obtain the second sequence.

Second solution - flipping coin 1 and 2 - is complement (inverse) of first - flipping just coin 3. First has 1 change, second 2 - sum is 3, the number of coins.

Conclusion: if you found minimum number of changes, maximum must be the inverse, that is, flipping all other coins. Number of changes is just the difference between the number of coins and the number of changes for minimum.

Example 6 coins

Possible sequences:

  • 0, 1, 0, 1, 0, 1
  • 1, 0, 1, 0, 1, 0

Starting with 1, 0, 1, 0, 1, 1 (your example), we can flip:

  • coin number 6: 1, 0, 1, 0, 1, 0 - count 1
  • all but number 6: 0, 1, 0, 1, 0, 1 - count 5

Sum: 1 + 5 = 6, the number of coins

1 otherwise we would have an infinite number of possible moves - flipping a coin twice (four, six, ... times) would produce the same result

Upvotes: 0

Related Questions