---
description: https://leetcode.com/problems/minimum-domino-rotations-for-equal-row/
---

# 1007. Minimum Domino Rotations For Equal Row

> In a row of dominoes,`A[i]`and`B[i]`represent the top and bottom halves of the`i`-th domino. (A domino is a tile with two numbers from 1 to 6 - one on each half of the tile.)
>
> We may rotate the`i`-th domino, so that`A[i]`and`B[i]`swap values.
>
> Return the minimum number of rotations so that all the values in`A`are the same, or all the values in`B` are the same.
>
> If it cannot be done, return`-1`.
>
> **Example 1:**
>
> ![](https://assets.leetcode.com/uploads/2019/03/08/domino.png)
>
> ```
> Input: 
> A = 
> [2,1,2,4,2,2]
> , B = 
> [5,2,6,2,3,2]
> Output: 
> 2
> Explanation: 
>
> The first figure represents the dominoes as given by A and B: before we do any rotations.
> If we rotate the second and fourth dominoes, we can make every value in the top row equal to 2, as indicated by the second figure.
> ```
>
> **Example 2:**
>
> ```
> Input: 
> A = 
> [3,5,1,2,3]
> , B = 
> [3,6,3,3,4]
> Output: 
> -1
> Explanation: 
>
> In this case, it is not possible to rotate the dominoes to make one row of values equal.
> ```

## Solution

两排六点骰子，问最少swap次数能使得其中一排数字相同。

1. 方法一: 依次遍历1\~6，看是否能满足
2. 法二：如果能使得两行数字相同，那数字必须是A\[0]或B\[0]。所以依次对A\[i]和B\[i]查是否等于A\[0]、B\[0]。如果A\[0]满足，就不需要查B\[0]了，因为只有当A\[0] == B\[0]时才可能A和B都满足条件。‌数个数时不能数==A\[0]或B\[0]的，因为A和B可能存在相同元素。

```cpp
class Solution {
public:
    int minDominoRotations(vector<int>& A, vector<int>& B) {
        int res = INT_MAX;
        for (int i = 1; i <= 6; ++i) {
            int ac = 0, bc = 0;
            bool f = true;
            for (int j = 0; j < A.size(); ++j) {
                if (A[j] == i) ++ac;
                if (B[j] == i) ++bc;
                if (!(A[j] == i || B[j] == i)) {
                    f = false;
                    break;
                }
            }
            if (f) {
                res = min(res, ((int)A.size()) - max(ac, bc));
            }
        }
        if (res == INT_MAX) return -1;
        return res;
    }
};
```

```cpp
class Solution {
public:
    int minDominoRotations(vector<int>& A, vector<int>& B) {
        if (A.size() != B.size()) return -1;
        auto n = A.size();
        for (int i = 0, a = 0, b = 0; i < n && (A[i] == A[0] || B[i] == A[0]); ++i) {
            if (A[i] != A[0]) ++a;
            if (B[i] != A[0]) ++b;
            if (i == A.size() - 1) return min(a, b); 
        } 
        for (int i = 0, a = 0, b = 0; i < n && (A[i] == B[0] || B[i] == B[0]); ++i) {
            if (A[i] != B[0]) ++a;
            if (B[i] != B[0]) ++b;
            if (i == n - 1) return min(a, b); 
        } 

        return -1;
    }
};
```
