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#
Count the number of each color (R, G, B) in the input array
The minimum number of remaining Quxes depends on the counts modulo 3
If all three counts have the same remainder when divided by 3, the minimum is the maximum of the three counts
Otherwise, the minimum is determined by the mathematical relationship between the remainders
Key insight: transformations preserve certain invariants related to the count differences
Code#
Cpp
Go
Java
Python
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#
Convert the problem into a counting problem for each color
Simulate transformations by reducing counts of two different colors and increasing the third
Use a greedy approach: always try to balance the counts to minimize the final result
Continue until no more transformations are possible
Apply mathematical shortcuts when patterns are detected
Code#
Cpp
Go
Java
Python
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