Find minimum elements after considering all possible transformations - GeeksforGeeks
Given an array of three colors. The array elements have a special property. Whenever two elements of different colors become adjacent to each other, they merge into an element of the third color. How many minimum number of elements can be there in array after considering all possible transformations.
Read full article from Find minimum elements after considering all possible transformations - GeeksforGeeks
Given an array of three colors. The array elements have a special property. Whenever two elements of different colors become adjacent to each other, they merge into an element of the third color. How many minimum number of elements can be there in array after considering all possible transformations.
Let n be number of elements in array. No matter what the input is, we always end up in three types of outputs:
- n: When no transformation can take place at all
- 2: When number of elements of each color are all odd or all even
- 1: When number of elements of each color are mix of odd and even
Steps:
1) Count the number of elements of each color. 2) Then only one out of the folowing four cases can happen: ......1) There are elements of only one color, return n. ......2) There are even number of elements of each color, return 2. ......3) There are odd number of elements of each color, return 2. ......4) In every other case, return 1. (The elements will combine with each other repeatedly until only one of them is left)
// Returns minium possible elements after considering
// all possible transformations.
int
findMin(
char
arr[],
int
n)
{
// Initialize counts of all colors as 0
int
b_count = 0, g_count = 0, r_count = 0;
// Count number of elements of different colors
for
(
int
i = 0; i < n; i++)
{
if
(arr[i] ==
'B'
) b_count++;
if
(arr[i] ==
'G'
) g_count++;
if
(arr[i] ==
'R'
) r_count++;
}
// Check if elements are of same color
if
(b_count==n || g_count==n || r_count==n)
return
n;
// If all are odd, return 2
if
((r_count&1 && g_count&1 && b_count&1) )
return
2;
// If all are even, then also return 2
if
(!(r_count & 1) && !(g_count & 1) &&
!(b_count & 1) )
return
2;
// If none above the cases are true, return 1
return
1;
}
Read full article from Find minimum elements after considering all possible transformations - GeeksforGeeks