Welcome to Subscribe On Youtube

954. Array of Doubled Pairs

Description

Given an integer array of even length arr, return true if it is possible to reorder arr such that arr[2 * i + 1] = 2 * arr[2 * i] for every 0 <= i < len(arr) / 2, or false otherwise.

 

Example 1:

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

Example 2:

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

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].

 

Constraints:

• 2 <= arr.length <= 3 * 104
• arr.length is even.
• -105 <= arr[i] <= 105

Solutions

• Java
• C++
• Python
• Go

• class Solution {
      public boolean canReorderDoubled(int[] arr) {
          Map<Integer, Integer> freq = new HashMap<>();
          for (int v : arr) {
              freq.put(v, freq.getOrDefault(v, 0) + 1);
          }
          if ((freq.getOrDefault(0, 0) & 1) != 0) {
              return false;
          }
          List<Integer> keys = new ArrayList<>(freq.keySet());
          keys.sort(Comparator.comparingInt(Math::abs));
          for (int k : keys) {
              if (freq.getOrDefault(k << 1, 0) < freq.get(k)) {
                  return false;
              }
              freq.put(k << 1, freq.getOrDefault(k << 1, 0) - freq.get(k));
          }
          return true;
      }
  }
  

• class Solution {
  public:
      bool canReorderDoubled(vector<int>& arr) {
          unordered_map<int, int> freq;
          for (int& v : arr) ++freq[v];
          if (freq[0] & 1) return false;
          vector<int> keys;
          for (auto& [k, _] : freq) keys.push_back(k);
          sort(keys.begin(), keys.end(), [](int a, int b) { return abs(a) < abs(b); });
          for (int& k : keys) {
              if (freq[k * 2] < freq[k]) return false;
              freq[k * 2] -= freq[k];
          }
          return true;
      }
  };
  

• class Solution:
      def canReorderDoubled(self, arr: List[int]) -> bool:
          freq = Counter(arr)
          if freq[0] & 1:
              return False
          for x in sorted(freq, key=abs):
              if freq[x << 1] < freq[x]:
                  return False
              freq[x << 1] -= freq[x]
          return True
  
  

• func canReorderDoubled(arr []int) bool {
  	freq := make(map[int]int)
  	for _, v := range arr {
  		freq[v]++
  	}
  	if freq[0]%2 != 0 {
  		return false
  	}
  	var keys []int
  	for k := range freq {
  		keys = append(keys, k)
  	}
  	sort.Slice(keys, func(i, j int) bool {
  		return abs(keys[i]) < abs(keys[j])
  	})
  	for _, k := range keys {
  		if freq[k*2] < freq[k] {
  			return false
  		}
  		freq[k*2] -= freq[k]
  	}
  	return true
  }
  
  func abs(x int) int {
  	if x < 0 {
  		return -x
  	}
  	return x
  }
  

All Problems

All Solutions