869. Reordered Power of 2 #

Problem #

Starting with a positive integer N, we reorder the digits in any order (including the original order) such that the leading digit is not zero.

Return true if and only if we can do this in a way such that the resulting number is a power of 2.

Example 1:

Input:1
Output:true

Example 2:

Input:10
Output:false

Example 3:

Input:16
Output:true

Example 4:

Input:24
Output:false

Example 5:

Input:46
Output:true

Note:

1 <= N <= 10^9

Problem Summary #

Given a positive integer N, we reorder its digits in any order (including the original order), noting that the leading digit cannot be zero. If we can obtain a power of 2 in this way, return true; otherwise, return false.

Solution Ideas #

Treat all permutations of the digits of the integer as strings, then the problem is transformed into determining whether these strings are consistent with the strings of powers of 2. There are many ways to determine this; here the author uses a map. For two strings with different permutations to be equal, the frequencies of all characters must be the same. Use a map to count the frequencies of their respective characters, and if they are all consistent in the end, then the two strings are determined to satisfy the problem requirements.
The data size of this problem is relatively small. In the interval [1,10^9], there are only about 30 powers of 2, so the strings that ultimately need to be checked are just these 30 or so. The author does not use a lookup table here, but adopts a more general approach. Even with a larger data size, this solution code can pass.

Code #

package leetcode

import "fmt"

func reorderedPowerOf2(n int) bool {
	sample, i := fmt.Sprintf("%v", n), 1
	for len(fmt.Sprintf("%v", i)) <= len(sample) {
		t := fmt.Sprintf("%v", i)
		if len(t) == len(sample) && isSame(t, sample) {
			return true
		}
		i = i << 1
	}
	return false
}

func isSame(t, s string) bool {
	m := make(map[rune]int)
	for _, v := range t {
		m[v]++
	}
	for _, v := range s {
		m[v]--
		if m[v] < 0 {
			return false
		}
		if m[v] == 0 {
			delete(m, v)
		}
	}
	return len(m) == 0
}