Leetcode: Array of Doubled Pairs

Array of Doubled Pairs



Similar Problems:


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

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


  • Solution:
// Blog link: https://code.dennyzhang.com/array-of-doubled-pairs
// Basic Ideas: sort + hashmap
// Complexity: Time O(n*log(n)), Space O(n)
import "sort"
func canReorderDoubled(A []int) bool {
    sort.Ints(A)
    m := map[int]int{}
    for _, num := range A {
        m[num]++
    }
    count := 0
    for _, num := range A {
        if m[num] > 0 {
            if num<0 && num%2 !=0 { return false }
                        num2 := num*2
            if num<0 { num2 = num/2 }
            m[num]--
            count++

            if m[num2]>0 {
                m[num2]--
                count++
            } else {
                return false
            }
        }
        if count == len(A) {
            return true
        }
    }
    return count == len(A)
}
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.