【位运算】【脑筋急转弯】2749. 得到整数零需要执行的最少操作数

作者推荐

视频算法专题

本文涉及知识点

2749. 得到整数零需要执行的最少操作数

给你两个整数：num1 和 num2 。
在一步操作中，你需要从范围 [0, 60] 中选出一个整数 i ，并从 num1 减去 2i + num2 。
请你计算，要想使 num1 等于 0 需要执行的最少操作数，并以整数形式返回。
如果无法使 num1 等于 0 ，返回 -1 。
示例 1：
输入：num1 = 3, num2 = -2
输出：3
解释：可以执行下述步骤使 3 等于 0 ：

选择 i = 2 ，并从 3 减去 22 + (-2) ，num1 = 3 - (4 + (-2)) = 1 。
选择 i = 2 ，并从 1 减去 22 + (-2) ，num1 = 1 - (4 + (-2)) = -1 。
选择 i = 0 ，并从 -1 减去 20 + (-2) ，num1 = (-1) - (1 + (-2)) = 0 。
可以证明 3 是需要执行的最少操作数。
示例 2：
输入：num1 = 5, num2 = 7
输出：-1
解释：可以证明，执行操作无法使 5 等于 0 。
提示：
1 <= num1 <= 10⁹
-10⁹ <= num2 <= 10⁹

脑筋急转弯

特殊情况

num2为0，2^x 能通过y次操作变成0，求y的取值范围。
x == 1时，只能i 取0，故y $\in$ [1,1]。
x == 2时，2¹,y == 1 ; 2⁰+2⁰,y==2，故y $\in$ [1,2]。
x == 4 时，y $\in$ [1,4] , 2² , 2 ¹ + 2¹ , 2¹+2⁰+2⁰ , 2⁰+2⁰+2⁰+2⁰。
猜测：2^m 可以通过[1,2^m]操作变成0。
m = 0，只能取1。
证明： m >=0 , 2^m的操作次数f(m)范围是[1,2^m]，则2^m+1的操作次数范围是[1,2^m+1]。
f(m+1)=f(m)+f(m) ，故f(m+1) $\in$ [2,2*2^m]即[2,2^m+1]。
直接减2^m+1，操作次数就是1。故： f(m+1) $\in$ [1,2^m+1]。
任意数都可以表示为：2^m1+2^m2 $\cdots$ 2^mo
当num2为零时：num1的操作次数的合法范围是：[num1中1的位数，num1]。

分析

特殊情况无需排除：num1为0，结果为0。
令操作y1次后，还需要减去 num3 = num1 - num2*y1。如果y1 $\in$ [num3中1的个数，num3] 则可以让结果为0。
num3必须大于等于0，这条无需额外判断，因为y1 必须小于等于num3。如果num3为0，这条不符合。

当y1等于64，一定大于num3中1的个数。如果y1 <= num3，则结果至少是64。如果此时无解，说明：64 > num3。
如果num2 >= 0，num不会变大，则num3永远不会变大，即永远不会大于y1。
如果num2 < 0，则num1取最小值0，num2取最大值-1，则nums3 = 64,和小于64矛盾。

当y1 <=64，则num3的取值范围：10⁹*64 ,最多近40个二进制一。故只需要枚举y1 $\in$ [0,40]。

代码

核心代码

class CBitCounts
{
public:
	CBitCounts(int iMaskCount)
	{
		for (int i = 0; i < iMaskCount; i++)
		{
			m_vCnt.emplace_back(bitcount(i));
		}
	}
	template<class T>
	static int bitcount(T x) {
		int countx = 0;
		while (x) {
			countx++;
			x &= (x - 1);
		}
		return countx;
	}
	vector<int> m_vCnt;
};
class Solution {
public:
	int makeTheIntegerZero(int num1, int num2) {
		for (long long i = 0; i < 61; i++)
		{
			const long long llNeed = num1 - num2 * i;
			const int iOneCnt = CBitCounts::bitcount((unsigned long long)llNeed);
			if ( (i  >= iOneCnt)&&(i <= llNeed))
			{
				return i;
			}
		}
		return -1;
	}
};

测试用例

template<class T,class T2>
void Assert(const T& t1, const T2& t2)
{
	assert(t1 == t2);
}

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}

}

int main()
{
	int num1, num2;
	{
		Solution sln;
		num1 =3 ,num2 = -2 ;
		auto res = sln.makeTheIntegerZero(num1, num2);
		Assert(3, res);
	}
	{
		Solution sln;
		num1 = 5, num2 = 7;
		auto res = sln.makeTheIntegerZero(num1, num2);
		Assert(-1, res);
	}
}

2023年6月

class Solution {
public:
int makeTheIntegerZero(int num1, int num2) {
if (0 == num1)
{
return 0;
}
unsigned long long n = num1;
for (int i = 1; i <= 60; i++)
{
n -= num2;
if (n >= 0 && Is(n,i))
{
return i;
}
}
return -1;
}
bool Is(unsigned long long n, int iCi)
{
if (n >= ((long long)1 << 61))
{
return false;
}
long long iCanSub = bitcount(n);
if (iCanSub > iCi)
{
return false;
}
if (bitcount(n) == iCi)
{
return true;
}
for (int i = 1; i <= 60; i++)
{
if (n & (1LL << i))
{
iCanSub += (1LL << i) - 1;
}
}
return iCanSub >= iCi;
}
};

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛