[Leetcode] 869. Reorder to a power of 2

Title Description:

Starting with a positive integer N, we reorder the numbers in any order, including the original order, noting that their leading numbers cannot be zero.

If we can get a power of 2 by doing this, return true; otherwise, return false.

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

Tips:

  1. 1 <= N <= 10^9

Solving ideas:

The idea behind this question is to give a list of numbers whose first number is not 0 and whose power of 2 returns true in all permutations.

AC code:

class Solution {
public:
   bool reorderedPowerOf2(int n) {
	int tmp;
	vector<int> a;
	while (n>0)
	{
		a.push_back(n % 10);
		n /= 10;
	}
	sort(a.begin(), a.end());
	do
	{
		if (a[0] == 0) continue;
		tmp = 0;
		for (int i = 0; i<a.size(); i++)
			tmp = tmp * 10 + a[i];
		for (int i = 0; i<30; i++)
			if (tmp == (1 << i)) return true;
	} while (next_permutation(a.begin(), a.end()));
	return false;
  }
};
    

Personal attempts (memory overrun):

Actually, this is my original code, but I can't get over it, memory overrun, feeling should be caused by a full array of recursive processes, but I don't know how to solve it.If you have a solution, I would like to give you some advice. Thank you first.

bool Powerof2(int n)
{
	while (n>1)
	{
		if (n % 2 == 1)return false;
		n = n / 2;
	}
	return true;
}
void Arrangement(vector<vector<int>>& res, vector<int> nums, int begin)
{
	if (begin == nums.size())
	{
		res.push_back(nums);
		return;
	}
	for (int i = begin; i < nums.size(); ++i)
	{
		if (i == begin || nums[i] != nums[begin])
		{
			swap(nums[i], nums[begin]);
			Arrangement(res, nums, begin + 1);
			swap(nums[i], nums[begin]);
		}
	}
}
bool reorderedPowerOf2(int N) 
{
	vector<int> nums;
	while (N)
	{
		nums.push_back(N % 10);
		N = N / 10;
	}
	vector<vector<int>> res;
	Arrangement(res, nums, 0);
	for (int i = 0; i < res.size(); i++)
	{
		if (res[i][0] == 0)continue;
		int n = 0;
		for (int j = 0; j < res[0].size(); j++)
		{
			n = n * 10 + res[i][j];
		}
		if(Powerof2(n)==true) return true;
	}
	return false;
}

 

Posted on Wed, 12 Feb 2020 08:58:45 -0800 by curtisdw