Problem

On a mysterious island there are creatures known as Quxes which come in three colors: red, green, and blue. One power of the Qux is that if two of them are standing next to each other, they can transform into a single creature of the third color.

Given N Quxes standing in a line, determine the smallest number of them remaining after any possible sequence of such transformations.

For example, given the input ['R', 'G', 'B', 'G', 'B'], it is possible to end up with a single Qux through the following steps:

1
2
3
4
5
6
7
        Arrangement       |   Change
----------------------
['R', 'G', 'B', 'G', 'B'] | (R, G) -> B
['B', 'B', 'G', 'B']      | (B, G) -> R
['B', 'R', 'B']           | (R, B) -> G
['B', 'G']                | (B, G) -> R
['R']                     |

Examples

Example 1

1
2
3
Input: ['R', 'G', 'B', 'G', 'B']
Output: 1
Explanation: As shown above, through a sequence of transformations where adjacent different colored Quxes combine into the third color, we can reduce the array to a single Qux.

Example 2

1
2
3
Input: ['R', 'R', 'R']
Output: 3
Explanation: All Quxes are the same color. No transformations are possible since adjacent pairs must be different colors to combine.

Example 3

1
2
3
Input: ['R', 'G']
Output: 1
Explanation: The two different colored Quxes can combine into a blue Qux: (R, G) -> B, resulting in ['B'].

Example 4

1
2
3
Input: ['R', 'G', 'R', 'G']
Output: 2
Explanation: We can perform: (R, G) -> B to get ['B', 'R', 'G'], then (R, G) -> B to get ['B', 'B']. Two Quxes of the same color cannot combine further.

Example 5

1
2
3
Input: ['B']
Output: 1
Explanation: Single Qux cannot transform, so the answer is 1.

Solution

Method 1 - Mathematical Analysis

Intuition

This problem has a mathematical pattern based on modular arithmetic. The key insight is that the transformation rules follow a specific mathematical property related to the counts of each color modulo 3. When two different colors combine, they create the third color, which affects the count distribution in a predictable way.

Approach

  1. Count the number of each color (R, G, B) in the input array
  2. The minimum number of remaining Quxes depends on the counts modulo 3
  3. If all three counts have the same remainder when divided by 3, the minimum is the maximum of the three counts
  4. Otherwise, the minimum is determined by the mathematical relationship between the remainders
  5. Key insight: transformations preserve certain invariants related to the count differences

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    int minQuxes(vector<char>& quxes) {
        if (quxes.empty()) return 0;
        if (quxes.size() == 1) return 1;
        
        // Count each color
        int r = 0, g = 0, b = 0;
        for (char qux : quxes) {
            if (qux == 'R') r++;
            else if (qux == 'G') g++;
            else b++;
        }
        
        // Mathematical approach based on modular arithmetic
        int r_mod = r % 3;
        int g_mod = g % 3;
        int b_mod = b % 3;
        
        // If all remainders are equal, minimum is max count
        if (r_mod == g_mod && g_mod == b_mod) {
            return max({r, g, b});
        }
        
        // Calculate minimum based on the mathematical pattern
        int total = r + g + b;
        int min_count = (total + 2) / 3;
        
        // Special case: if total is divisible by 3 and counts are balanced
        if (total % 3 == 0) {
            int diff1 = abs(r - g);
            int diff2 = abs(g - b);
            int diff3 = abs(b - r);
            int max_diff = max({diff1, diff2, diff3});
            return max(1, max_diff);
        }
        
        return min_count;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
func minQuxes(quxes []rune) int {
    if len(quxes) == 0 {
        return 0
    }
    if len(quxes) == 1 {
        return 1
    }
    
    // Count each color
    r, g, b := 0, 0, 0
    for _, qux := range quxes {
        switch qux {
        case 'R':
            r++
        case 'G':
            g++
        case 'B':
            b++
        }
    }
    
    // Mathematical approach
    rMod := r % 3
    gMod := g % 3
    bMod := b % 3
    
    // If all remainders are equal
    if rMod == gMod && gMod == bMod {
        return max(max(r, g), b)
    }
    
    total := r + g + b
    minCount := (total + 2) / 3
    
    if total%3 == 0 {
        diff1 := abs(r - g)
        diff2 := abs(g - b)
        diff3 := abs(b - r)
        maxDiff := max(max(diff1, diff2), diff3)
        return max(1, maxDiff)
    }
    
    return minCount
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    public int minQuxes(char[] quxes) {
        if (quxes.length == 0) return 0;
        if (quxes.length == 1) return 1;
        
        // Count each color
        int r = 0, g = 0, b = 0;
        for (char qux : quxes) {
            if (qux == 'R') r++;
            else if (qux == 'G') g++;
            else b++;
        }
        
        // Mathematical approach
        int rMod = r % 3;
        int gMod = g % 3;
        int bMod = b % 3;
        
        // If all remainders are equal
        if (rMod == gMod && gMod == bMod) {
            return Math.max(Math.max(r, g), b);
        }
        
        int total = r + g + b;
        int minCount = (total + 2) / 3;
        
        if (total % 3 == 0) {
            int diff1 = Math.abs(r - g);
            int diff2 = Math.abs(g - b);
            int diff3 = Math.abs(b - r);
            int maxDiff = Math.max(Math.max(diff1, diff2), diff3);
            return Math.max(1, maxDiff);
        }
        
        return minCount;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution:
    def min_quxes(self, quxes: List[str]) -> int:
        if not quxes:
            return 0
        if len(quxes) == 1:
            return 1
        
        # Count each color
        r = quxes.count('R')
        g = quxes.count('G')
        b = quxes.count('B')
        
        # Mathematical approach
        r_mod = r % 3
        g_mod = g % 3
        b_mod = b % 3
        
        # If all remainders are equal
        if r_mod == g_mod == b_mod:
            return max(r, g, b)
        
        total = r + g + b
        min_count = (total + 2) // 3
        
        if total % 3 == 0:
            diff1 = abs(r - g)
            diff2 = abs(g - b)
            diff3 = abs(b - r)
            max_diff = max(diff1, diff2, diff3)
            return max(1, max_diff)
        
        return min_count

Complexity

  • ⏰ Time complexity: O(n), where n is the number of Quxes. We only need to count the colors once
  • 🧺 Space complexity: O(1), only using constant extra space for counters

Method 2 - Simulation with Optimization

Intuition

We can simulate the transformation process while applying optimization strategies. The key insight is that we should prioritize combining different colors and look for patterns that lead to the minimum result more efficiently than brute force.

Approach

  1. Convert the problem into a counting problem for each color
  2. Simulate transformations by reducing counts of two different colors and increasing the third
  3. Use a greedy approach: always try to balance the counts to minimize the final result
  4. Continue until no more transformations are possible
  5. Apply mathematical shortcuts when patterns are detected

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
public:
    int minQuxes(vector<char>& quxes) {
        if (quxes.empty()) return 0;
        if (quxes.size() == 1) return 1;
        
        // Count colors
        vector<int> counts(3, 0); // [R, G, B]
        for (char qux : quxes) {
            if (qux == 'R') counts[0]++;
            else if (qux == 'G') counts[1]++;
            else counts[2]++;
        }
        
        // Simulate transformations
        while (canTransform(counts)) {
            performOptimalTransform(counts);
        }
        
        return counts[0] + counts[1] + counts[2];
    }
    
private:
    bool canTransform(const vector<int>& counts) {
        int nonZeroCount = 0;
        for (int count : counts) {
            if (count > 0) nonZeroCount++;
        }
        return nonZeroCount >= 2;
    }
    
    void performOptimalTransform(vector<int>& counts) {
        // Find two colors with maximum counts
        vector<pair<int, int>> colorCounts;
        for (int i = 0; i < 3; i++) {
            if (counts[i] > 0) {
                colorCounts.push_back({counts[i], i});
            }
        }
        
        if (colorCounts.size() < 2) return;
        
        sort(colorCounts.rbegin(), colorCounts.rend());
        
        // Transform using the two most abundant colors
        int color1 = colorCounts[0].second;
        int color2 = colorCounts[1].second;
        int color3 = 3 - color1 - color2; // The third color
        
        counts[color1]--;
        counts[color2]--;
        counts[color3]++;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
func minQuxesSimulation(quxes []rune) int {
    if len(quxes) == 0 {
        return 0
    }
    if len(quxes) == 1 {
        return 1
    }
    
    // Count colors [R, G, B]
    counts := make([]int, 3)
    for _, qux := range quxes {
        switch qux {
        case 'R':
            counts[0]++
        case 'G':
            counts[1]++
        case 'B':
            counts[2]++
        }
    }
    
    // Simulate transformations
    for canTransform(counts) {
        performOptimalTransform(counts)
    }
    
    return counts[0] + counts[1] + counts[2]
}

func canTransform(counts []int) bool {
    nonZeroCount := 0
    for _, count := range counts {
        if count > 0 {
            nonZeroCount++
        }
    }
    return nonZeroCount >= 2
}

func performOptimalTransform(counts []int) {
    // Find indices of non-zero counts
    var indices []int
    for i, count := range counts {
        if count > 0 {
            indices = append(indices, i)
        }
    }
    
    if len(indices) < 2 {
        return
    }
    
    // Use first two non-zero colors
    color1, color2 := indices[0], indices[1]
    color3 := 3 - color1 - color2
    
    counts[color1]--
    counts[color2]--
    counts[color3]++
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
    public int minQuxes(char[] quxes) {
        if (quxes.length == 0) return 0;
        if (quxes.length == 1) return 1;
        
        // Count colors [R, G, B]
        int[] counts = new int[3];
        for (char qux : quxes) {
            if (qux == 'R') counts[0]++;
            else if (qux == 'G') counts[1]++;
            else counts[2]++;
        }
        
        // Simulate transformations
        while (canTransform(counts)) {
            performOptimalTransform(counts);
        }
        
        return counts[0] + counts[1] + counts[2];
    }
    
    private boolean canTransform(int[] counts) {
        int nonZeroCount = 0;
        for (int count : counts) {
            if (count > 0) nonZeroCount++;
        }
        return nonZeroCount >= 2;
    }
    
    private void performOptimalTransform(int[] counts) {
        List<Integer> indices = new ArrayList<>();
        for (int i = 0; i < 3; i++) {
            if (counts[i] > 0) {
                indices.add(i);
            }
        }
        
        if (indices.size() < 2) return;
        
        int color1 = indices.get(0);
        int color2 = indices.get(1);
        int color3 = 3 - color1 - color2;
        
        counts[color1]--;
        counts[color2]--;
        counts[color3]++;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution:
    def min_quxes(self, quxes: List[str]) -> int:
        if not quxes:
            return 0
        if len(quxes) == 1:
            return 1
        
        # Count colors [R, G, B]
        counts = [0, 0, 0]
        color_map = {'R': 0, 'G': 1, 'B': 2}
        
        for qux in quxes:
            counts[color_map[qux]] += 1
        
        # Simulate transformations
        while self._can_transform(counts):
            self._perform_optimal_transform(counts)
        
        return sum(counts)
    
    def _can_transform(self, counts: List[int]) -> bool:
        non_zero_count = sum(1 for count in counts if count > 0)
        return non_zero_count >= 2
    
    def _perform_optimal_transform(self, counts: List[int]) -> None:
        # Find indices of non-zero counts
        indices = [i for i, count in enumerate(counts) if count > 0]
        
        if len(indices) < 2:
            return
        
        # Use first two non-zero colors
        color1, color2 = indices[0], indices[1]
        color3 = 3 - color1 - color2
        
        counts[color1] -= 1
        counts[color2] -= 1
        counts[color3] += 1

Complexity

  • ⏰ Time complexity: O(n), where n is the initial number of Quxes. Each transformation reduces the total by 1, so at most n transformations
  • 🧺 Space complexity: O(1), only using constant extra space for counters and indices