【位运算】【脑筋急转弯】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

相关

下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版

https://download.csdn.net/download/he_zhidan/88348653

测试环境

操作系统：win7 开发环境： VS2019 C++17

或者 操作系统：win10 开发环境： VS2022 C++17

如无特殊说明，本算法用**C++**实现。