# [LeetCode 954. Array of Doubled Pairs ](https://leetcode.com/explore/challenge/card/august-leetcoding-challenge-2021/614/week-2-august-8th-august-14th/3877/)
### Daily challenge Aug 11, 2021 (MEDIAN)

>Given an array of integers `arr` of even length, return `true` if and only if it is possible to reorder it such that **`arr[2 * i + 1] = 2 * arr[2 * i]`** for every `0 <= i < len(arr) / 2`.

:::info
**Example 1:**
**Input:** arr = [3,1,3,6]
**Output:** false
:::

:::info
**Example 2:**
**Input:** arr = [2,1,2,6]
**Output:** false
:::

:::info
**Example 3:**
**Input:** arr = [4,-2,2,-4]
**Output:** true
**Explanation:** We can take two groups, [-2,-4] and [2,4] to form [-2,-4,2,4] or [2,4,-2,-4].
:::

:::info
**Example 4:**
**Input:** arr = [1,2,4,16,8,4]
**Output:** false
:::

:::warning
**Constraints:**
* 0 <= arr.length <= 3 * 104
* arr.length is even.
* -105 <= arr[i] <= 105
:::

---

### Approach 1 : Map
**`76 ms ( 94.57% )`** **`O()`**

* 先用 **`map<int, int> list`** 紀錄每個 `arr[]` 出現次數。
* 遍歷 `list`，**`key`** 代表 `arr[]` 中的元素、**`count`** 代表出現次數。
> 可以分為三種情況。
> 1. **`key == 0`**
>> * 因為 `0 * 2 = 2` ，所以只需判斷 `count` 是否可以整除 `2`。
> 2. **`key > 0`**
>> * 判斷 `list[key * 2]` 是否大於 `count`。
> 3. **`key < 0`**
>> * 判斷 `list[key / 2]` 是否大於 `count`。
>> * 因為 `map` 是由小到大排序，假設遇到**負數**，就會出現狀況。
>> ---> **`key = -4`**，我們應該要找到 **`-2`** 而不是 **`-8`**。
>> 所以應該尋找 **`list[key / 2]`**。
>> * 但這時又會出現一個問題，當 `key` 是**奇數**的話，就不可能找到答案，所以要特別判斷。

class Solution {
public:
    bool canReorderDoubled(vector<int>& arr) {
        map<int, int> list;
        
        for(auto val : arr){
            list[val]++;
        }
        
        for(auto current : list){
            int key = current.first;
            int count = current.second;
            
            if(key == 0){   
                if(count % 2 != 0)   return false;
            }
            else if(key > 0){
                if(list[key * 2] < count)    return false;
                else{
                    if(list[key * 2] == count)  list.erase(key * 2);
                    else    list[key * 2] -= count;
                }
            }
            else{
                if(key % 2 != 0)    return false;
                else if(list[key / 2] < count)    return false;
                else{
                    if(list[key / 2] == count)  list.erase(key / 2);
                    else    list[key / 2] -= count;
                }
            }
        }
        return true;
    }
};