FastPrepFastPrep
Problem Brief

Minimum Domino Removals

FULLTIMEOA
See Microsoft online assessment and hiring insights

A domino is a rectangular tile divided into two square parts. There are between 1 and 6 dots on each of the parts. There is an array A of length 2*N, representing N dominoes. Dominoes are arranged in a line in the order in which they appear in array A. The number of dots on the left and the right parts of the K-th domino are A[2*K] and A[2*K+1], respectively. For example, an array A = [2, 4, 1, 3, 4, 6, 2, 4, 1, 6] represents a sequence of five domino tiles: (2,4), (1,3), (4,6), (2,4), and (1,6).

In a correct domino sequence, each pair of neighboring tiles should have the same number of dots on their adjacent parts. For example, tiles (2, 4) and (4, 6) form a correct domino sequence and tiles (2, 4) and (1, 3) do not. What is the minimum number of domino tiles that must be removed from the sequence so that the remaining tiles form a correct domino sequence? It is not allowed to reorder or rotate the dominoes.

Function Description

Given an array A representing a sequence of N domino tiles, returns the minimum number of tiles that must be removed so that the remaining tiles form a correct domino sequence.

1Example 1

Input
A = [2, 4, 1, 3, 4, 6, 2, 4, 1, 6]
Output
3
Explanation
Example 1 illustration
The second and the last two dominoes should be removed. After this, the remaining dominoes are (2, 4) and (4, 6).

2Example 2

Input
A = [5, 1, 2, 6, 6, 1, 3, 1, 4, 3, 4, 6, 1, 2, 4, 1, 6, 21]
Output
7
Explanation
The domino tiles that should remain are: (2, 6), (6, 1), (1,2).

3Example 3

Input
A = [1, 5, 3, 3, 1, 31]
Output
2
Explanation
No pair of dominoes can be connected without rotating or reordering them.

Constraints

Limits and guarantees your solution can rely on.

🍇🍇
public int minNumTiles(int[] A) {
  // Write your code here :)
}
Input

A

[2, 4, 1, 3, 4, 6, 2, 4, 1, 6]

Output

3

Sign in to submit your solution.