Array of Doubled Pairs

Description

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

 

Example 1:

Input: [3,1,3,6]
Output: false

Example 2:

Input: [2,1,2,6]
Output: false

Example 3:

Input: [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].

Example 4:

Input: [1,2,4,16,8,4]
Output: false

 

Note:

1. 0 <= A.length <= 30000
2. A.length is even
3. -100000 <= A[i] <= 100000

Solution(javascript)

// /** Greedy O(nlog(n))
//  * @param {number[]} A
//  * @return {boolean}
//  */
// const canReorderDoubled = function (A) {
//   A.sort((a, b) => a - b)
//   let count = 0
//   const map = {}
//   for (const num of A) {
//     if (map[num / 2] > 0) {
//       map[num / 2] -= 1
//       count -= 1
//     } else if (map[num * 2] > 0) { // 负数的情况
//       map[num * 2] -= 1
//       count -= 1
//     } else {
//       map[num] = (map[num] || 0) + 1
//       count += 1
//     }
//   }
//   return count === 0
// }


/**
 * @param {number[]} A
 * @return {boolean}
 */
const canReorderDoubled = function (A) {
  const map = A.reduce((acc, num) => {
    acc[num] = (acc[num] || 0) + 1
    return acc
  }, {})
  const keys = Object.keys(map)
    .map(key => Number(key))
    .sort((a, b) => a - b)
  for (const key of keys) {
    if (key < 0) {
      while (map[key] > 0) {
        if (map[key / 2] > 0) {
          map[key] -= 1
          map[key / 2] -= 1
        } else {
          return false
        }
      }
    } else {
      while (map[key] > 0) {
        if (map[key * 2] > 0) {
          map[key] -= 1
          map[key * 2] -= 1
        } else {
          return false
        }
      }
    }
  }
  return true
}