Formatted question description: https://leetcode.ca/all/954.html

954. Array of Doubled Pairs (Medium)

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

Companies:
Google

Related Topics:
Array, Hash Table

Solution 1. Greedy

// OJ: https://leetcode.com/problems/array-of-doubled-pairs/
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
    bool canReorderDoubled(vector<int>& A) {
        multiset<int> s(A.begin(), A.end());
        while (s.size()) {
            int val = *s.begin();
            if (val < 0 && val % 2) return false;
            int next = val >= 0 ? val * 2 : val / 2;
            s.erase(s.begin());
            auto it = s.find(next);
            if (it == s.end()) return false;
            s.erase(it);
        }
        return true;
    }
};

Java

• Java
• C++
• Python

• class Solution {
      public boolean canReorderDoubled(int[] A) {
          List<Integer> list = new ArrayList<Integer>();
          int length = A.length;
          for (int i = 0; i < length; i++)
              list.add(A[i]);
          Collections.sort(list, new Comparator<Integer>() {
              public int compare(Integer num1, Integer num2) {
                  if (Math.abs(num1) != Math.abs(num2))
                      return Math.abs(num1) - Math.abs(num2);
                  else
                      return num1 - num2;
              }
          });
          while (list.size() > 0) {
              int num = list.remove(0);
              int num2 = num * 2;
              int index = list.indexOf(num2);
              if (index >= 0)
                  list.remove(index);
              else
                  return false;
          }
          return true;
      }
  }
  

• // OJ: https://leetcode.com/problems/array-of-doubled-pairs/
  // Time: O(NlogN)
  // Space: O(N)
  class Solution {
  public:
      bool canReorderDoubled(vector<int>& A) {
          multiset<int> s(A.begin(), A.end());
          while (s.size()) {
              int val = *s.begin();
              if (val < 0 && val % 2) return false;
              int next = val >= 0 ? val * 2 : val / 2;
              s.erase(s.begin());
              auto it = s.find(next);
              if (it == s.end()) return false;
              s.erase(it);
          }
          return true;
      }
  };
  

• class Solution(object):
      def canReorderDoubled(self, A):
          """
          :type A: List[int]
          :rtype: bool
          """
          A.sort()
          N = len(A)
          count = collections.Counter(A)
          for i in range(N):
              if A[i] == 0 or A[i] not in count: continue
              elif A[i] < 0:
                  if A[i] % 2 == 1 or count[A[i] / 2] == 0:
                      return False
                  else:
                      count[A[i] / 2] -= count[A[i]]
                      if count[A[i] / 2] == 0:
                          del count[A[i] / 2]
                      del count[A[i]]
              else:
                  if count[A[i] * 2] == 0:
                      return False
                  else:
                      count[A[i] * 2] -= count[A[i]]
                      if count[A[i] * 2] == 0:
                          del count[A[i] * 2]
                      del count[A[i]]
          return True
  

All Problems

All Solutions