mardi 27 avril 2021

Two Parts: Reading arrays and switching values to be alternating, then finding the minimum number of switches needed

I've been working on an specific interview question that basically asks the following: "There are N coins, each showing either heads or tails. We would like all the coins to be alternating between heads and tails. What is the minimum number of coins to be reversed to achieve this?"

Array examples: A = [1, 0, 1, 0, 1, 1] (function should return "1"), A = [1, 1, 0, 1, 1] (function should return "2"), etc.

I'm working with Java SE 8 and am using the function given:

class Solution { public int solution(int[] A); }

I can't seem to figure out why when it loops through, it either fails or changes too many values (it doesn't always provide the minimum number of reverses). Please help!

Here is the code that I've written so far; which works for one of the test cases, but fails others:

class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
        if (A.length == 1) return 0;
        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;

        int revers = 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;
            }
            revers = Math.max(revers, count);
        }
        return result + revers;
    }
}

Aucun commentaire:

Enregistrer un commentaire