Happy Residents

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
6 upvotes
Asked in company
American Express

Problem statement

Ninja town has ‘N’ houses along a street. The houses are either painted red or blue. The house colours are given in an integer array ‘color’, where 0 denotes the ith house is painted red, and 1 denotes the ith house is painted blue. The residents of a house will be happy if their house colour is different from both its neighbours if they exist. Hence, the Mayor decided to repaint some of the houses. But due to financial reasons, he wants to paint a minimum number of houses. Can you calculate the minimum number of houses that he needs to repaint?

Example: Suppose there are 3 houses and the colours [1, 1, 1], which means all the houses are coloured blue. If the Mayor repaints the second house to red, we will have the colours as [1, 0, 1]. We can see that all the neighbours will be happy. Hence, the minimum number of houses to be repainted is 1.

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains ‘T’, denoting the number of test cases.

The first line of each test case contains two integers, ‘N’ denoting the number of houses.

The second line of each test case contains an array ‘color’ containing ‘N’ space-separated integers.
Output Format: 
For each test case, print a single integer, denoting the minimum number of houses that need to be repainted.
Note: 
You are not required to print the expected output. It has already been taken care of. Just implement the function.
Constraints: 
1 <= T <= 10
1 <= N <= 10^5
0 <= color[i] <= 1

Time Limit: 1 sec
Sample Input 1:
2
4 
1 0 0 1
2
1 0
Sample Output 1:
2
0
Explanation for Sample Input 1:
In the first test case, the colours are [1, 0, 0, 1]. If we change the colours of the third and fourth houses, the colours will then be [1, 0, 1, 0]. Hence, the minimum number of houses to be repainted is 2.
In the second test case, we can see that all the residents are already happy. Hence, we do not need to repaint any house.
Sample Input 2:
2
2 
1 1
5
1 1 1 1 1
Sample Output 2:
1
2
Hint

Can we find a pattern of how the final colours will look like?

Approaches (1)
Greedy

If we closely look at the pattern of houses, we can see that the colours will have to be alternate with only the starting colour deciding all the other colours. Hence, the colours will be either [0, 1, 0, … ] or [1, 0, 1, …]. We will try making both the patterns and return the minimum value.



 

The steps are as follows:

  • Initialise Two variables ‘count1’ and ‘count2’ to 0, denoting the minimum houses to be repainted to get the first and second patterns, respectively.
  • Traverse from i = 0 to i = ‘N - 1’.
    • If the colour of the colour[i] does not match according to the first pattern.
      • Increment ‘count1’.
    • If the colour of the colour[i] does not match according to the second pattern.
      • Increment ‘count2’.
  • Return min(count1, count2).
Time Complexity

O(N), where ‘N’ is the number of houses.


 

There are two final color patterns, and we are checking both of them using a single traversal. Hence, the overall complexity is O(N).


 

Space Complexity

O(1).


 

We are using constant space.


 

Code Solution
(100% EXP penalty)
Happy Residents
Full screen
Console