Question

3007. 价值和小于等于 K 的最大数字

English Version

题目描述

给你一个整数 k 和一个整数 x 。

令 s 为整数 num 的下标从 1 开始的二进制表示。我们说一个整数 num 的 价值 是满足 i % x == 0 且 s[i] 是 设置位 的 i 的数目。

请你返回 最大 整数_ _num ，满足从 1 到 num 的所有整数的 价值 和小于等于 k 。

注意：

• 一个整数二进制表示下 设置位 是值为 1 的数位。
• 一个整数的二进制表示下标从右到左编号，比方说如果 s == 11100 ，那么 s[4] == 1 且 s[2] == 0 。

 

示例 1：

输入：k = 9, x = 1
输出：6
解释：数字 1 ，2 ，3 ，4 ，5 和 6 二进制表示分别为 "1" ，"10" ，"11" ，"100" ，"101" 和 "110" 。
由于 x 等于 1 ，每个数字的价值分别为所有设置位的数目。
这些数字的所有设置位数目总数是 9 ，所以前 6 个数字的价值和为 9 。
所以答案为 6 。

示例 2：

输入：k = 7, x = 2
输出：9
解释：由于 x 等于 2 ，我们检查每个数字的偶数位。
2 和 3 在二进制表示下的第二个数位为设置位，所以它们的价值和为 2 。
6 和 7 在二进制表示下的第二个数位为设置位，所以它们的价值和为 2 。
8 和 9 在二进制表示下的第四个数位为设置位但第二个数位不是设置位，所以它们的价值和为 2 。
数字 1 ，4 和 5 在二进制下偶数位都不是设置位，所以它们的价值和为 0 。
10 在二进制表示下的第二个数位和第四个数位都是设置位，所以它的价值为 2 。
前 9 个数字的价值和为 6 。
前 10 个数字的价值和为 8，超过了 k = 7 ，所以答案为 9 。

 

提示：

• 1 <= k <= 1015
• 1 <= x <= 8

解法

方法一

class Solution:
  def findMaximumNumber(self, k: int, x: int) -> int:
    @cache
    def dfs(pos, limit, cnt):
      if pos == 0:
        return cnt
      ans = 0
      up = (self.num >> (pos - 1) & 1) if limit else 1
      for i in range(up + 1):
        ans += dfs(pos - 1, limit and i == up, cnt + (i == 1 and pos % x == 0))
      return ans

    l, r = 1, 10**18
    while l < r:
      mid = (l + r + 1) >> 1
      self.num = mid
      v = dfs(mid.bit_length(), True, 0)
      dfs.cache_clear()
      if v <= k:
        l = mid
      else:
        r = mid - 1
    return l

class Solution {
  private int x;
  private long num;
  private Long[][] f;

  public long findMaximumNumber(long k, int x) {
    this.x = x;
    long l = 1, r = (long) 1e17;
    while (l < r) {
      long mid = (l + r + 1) >>> 1;
      num = mid;
      f = new Long[65][65];
      int pos = 64 - Long.numberOfLeadingZeros(mid);
      if (dfs(pos, 0, true) <= k) {
        l = mid;
      } else {
        r = mid - 1;
      }
    }
    return l;
  }

  private long dfs(int pos, int cnt, boolean limit) {
    if (pos == 0) {
      return cnt;
    }
    if (!limit && f[pos][cnt] != null) {
      return f[pos][cnt];
    }
    long ans = 0;
    int up = limit ? (int) (num >> (pos - 1) & 1) : 1;
    for (int i = 0; i <= up; ++i) {
      ans += dfs(pos - 1, cnt + (i == 1 && pos % x == 0 ? 1 : 0), limit && i == up);
    }
    if (!limit) {
      f[pos][cnt] = ans;
    }
    return ans;
  }
}

class Solution {
public:
  long long findMaximumNumber(long long k, int x) {
    using ll = long long;
    ll l = 1, r = 1e17;
    ll num = 0;
    ll f[65][65];
    function<ll(int, int, bool)> dfs = [&](int pos, int cnt, bool limit) -> ll {
      if (pos == 0) {
        return cnt;
      }
      if (!limit && f[pos][cnt] != -1) {
        return f[pos][cnt];
      }
      int up = limit ? num >> (pos - 1) & 1 : 1;
      ll ans = 0;
      for (int i = 0; i <= up; ++i) {
        ans += dfs(pos - 1, cnt + (i == 1 && pos % x == 0), limit && i == up);
      }
      if (!limit) {
        f[pos][cnt] = ans;
      }
      return ans;
    };
    while (l < r) {
      ll mid = (l + r + 1) >> 1;
      num = mid;
      memset(f, -1, sizeof(f));
      int pos = 64 - __builtin_clzll(mid);
      if (dfs(pos, 0, true) <= k) {
        l = mid;
      } else {
        r = mid - 1;
      }
    }
    return l;
  }
};

func findMaximumNumber(k int64, x int) int64 {
  var l, r int64 = 1, 1e17
  var num int64
  var f [65][65]int64
  var dfs func(pos, cnt int, limit bool) int64
  dfs = func(pos, cnt int, limit bool) int64 {
    if pos == 0 {
      return int64(cnt)
    }
    if !limit && f[pos][cnt] != -1 {
      return f[pos][cnt]
    }
    var ans int64
    up := 1
    if limit {
      up = int(num >> (pos - 1) & 1)
    }
    for i := 0; i <= up; i++ {
      v := cnt
      if i == 1 && pos%x == 0 {
        v++
      }
      ans += dfs(pos-1, v, limit && i == up)
    }
    if !limit {
      f[pos][cnt] = ans
    }
    return ans
  }
  for l < r {
    mid := (l + r + 1) >> 1
    num = mid
    m := bits.Len(uint(num))
    for i := range f {
      for j := range f[i] {
        f[i][j] = -1
      }
    }
    if dfs(m, 0, true) <= k {
      l = mid
    } else {
      r = mid - 1
    }
  }
  return l
}