Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1012.html
1012. Complement of Base 10 Integer (Easy)
Every non-negative integer N
has a binary representation. For example, 5
can be represented as "101"
in binary, 11
as "1011"
in binary, and so on. Note that except for N = 0
, there are no leading zeroes in any binary representation.
The complement of a binary representation is the number in binary you get when changing every 1
to a 0
and 0
to a 1
. For example, the complement of "101"
in binary is "010"
in binary.
For a given number N
in base-10, return the complement of it's binary representation as a base-10 integer.
Example 1:
Input: 5 Output: 2 Explanation: 5 is "101" in binary, with complement "010" in binary, which is 2 in base-10.
Example 2:
Input: 7 Output: 0 Explanation: 7 is "111" in binary, with complement "000" in binary, which is 0 in base-10.
Example 3:
Input: 10 Output: 5 Explanation: 10 is "1010" in binary, with complement "0101" in binary, which is 5 in base-10.
Note:
0 <= N < 10^9
Companies:
Cloudera
Related Topics:
Math
Solution 1.
-
class Solution { public int numDupDigitsAtMostN(int N) { if (N <= 10) return 0; int duplicates = 0; int length = String.valueOf(N).length(); for (int i = 2; i < length; i++) duplicates += dupNums(i); Set<Integer> usedDigits = new HashSet<Integer>(); int curNum = (int) Math.pow(10, length - 1); int curLength = length - 1; int unit = curNum; boolean flag = false; while (unit > 1) { int lastDigit = N / unit % 10; int upperBound = N / unit * unit; while (curNum < upperBound) { int curDigit = curNum / unit % 10; int curCount = 0; if (!usedDigits.contains(curDigit)) { curCount = 1; int start = 9 - usedDigits.size(); for (int i = 0; i < curLength; i++) curCount *= start - i; } duplicates += unit - curCount; curNum += unit; } if (usedDigits.add(lastDigit)) { curLength--; unit /= 10; } else { flag = true; break; } } if (flag) duplicates += N - curNum + 1; else { while (curNum <= N) { int lastDigit = curNum % 10; if (usedDigits.contains(lastDigit)) duplicates++; curNum++; } } return duplicates; } public int dupNums(int length) { int distincts = 9; for (int i = 1; i < length; i++) distincts *= 10 - i; return 9 * (int) Math.pow(10, length - 1) - distincts; } } ############ class Solution { private int[] nums = new int[11]; private Integer[][] dp = new Integer[11][1 << 11]; public int numDupDigitsAtMostN(int n) { return n - f(n); } private int f(int n) { int i = -1; for (; n > 0; n /= 10) { nums[++i] = n % 10; } return dfs(i, 0, true, true); } private int dfs(int pos, int mask, boolean lead, boolean limit) { if (pos < 0) { return lead ? 0 : 1; } if (!lead && !limit && dp[pos][mask] != null) { return dp[pos][mask]; } int ans = 0; int up = limit ? nums[pos] : 9; for (int i = 0; i <= up; ++i) { if ((mask >> i & 1) == 1) { continue; } if (i == 0 && lead) { ans += dfs(pos - 1, mask, lead, limit && i == up); } else { ans += dfs(pos - 1, mask | 1 << i, false, limit && i == up); } } if (!lead && !limit) { dp[pos][mask] = ans; } return ans; } }
-
// OJ: https://leetcode.com/problems/complement-of-base-10-integer/ // Time: O(1) // Space: O(1) class Solution { public: int bitwiseComplement(int N) { if (!N) return 1; unsigned mask = ~0; while (mask & N) mask <<= 1; return ~N & ~mask; } };
-
class Solution: def numDupDigitsAtMostN(self, n: int) -> int: return n - self.f(n) def f(self, n): def A(m, n): return 1 if n == 0 else A(m, n - 1) * (m - n + 1) vis = [False] * 10 ans = 0 digits = [int(c) for c in str(n)[::-1]] m = len(digits) for i in range(1, m): ans += 9 * A(9, i - 1) for i in range(m - 1, -1, -1): v = digits[i] j = 1 if i == m - 1 else 0 while j < v: if not vis[j]: ans += A(10 - (m - i), i) j += 1 if vis[v]: break vis[v] = True if i == 0: ans += 1 return ans ############ class Solution(object): def bitwiseComplement(self, N): """ :type N: int :rtype: int """ return int("".join(map(lambda x :"0" if x == "1" else "1", bin(N)[2:])), 2)
-
func numDupDigitsAtMostN(n int) int { return n - f(n) } func f(n int) int { nums := []int{} for ; n > 0; n /= 10 { nums = append(nums, n%10) } dp := [11][1 << 11]int{} for i := range dp { for j := range dp[i] { dp[i][j] = -1 } } var dfs func(int, int, bool, bool) int dfs = func(pos int, mask int, lead bool, limit bool) int { if pos < 0 { if lead { return 0 } return 1 } if !lead && !limit && dp[pos][mask] != -1 { return dp[pos][mask] } up := 9 if limit { up = nums[pos] } ans := 0 for i := 0; i <= up; i++ { if mask>>i&1 == 1 { continue } if i == 0 && lead { ans += dfs(pos-1, mask, lead, limit && i == up) } else { ans += dfs(pos-1, mask|1<<i, false, limit && i == up) } } if !lead && !limit { dp[pos][mask] = ans } return ans } return dfs(len(nums)-1, 0, true, true) }
-
function numDupDigitsAtMostN(n: number): number { return n - f(n); } function f(n: number): number { const nums: number[] = []; let i = -1; for (; n; n = Math.floor(n / 10)) { nums[++i] = n % 10; } const dp = Array.from({ length: 11 }, () => Array(1 << 11).fill(-1)); const dfs = ( pos: number, mask: number, lead: boolean, limit: boolean, ): number => { if (pos < 0) { return lead ? 0 : 1; } if (!lead && !limit && dp[pos][mask] !== -1) { return dp[pos][mask]; } const up = limit ? nums[pos] : 9; let ans = 0; for (let i = 0; i <= up; ++i) { if ((mask >> i) & 1) { continue; } if (lead && i === 0) { ans += dfs(pos - 1, mask, lead, limit && i === up); } else { ans += dfs(pos - 1, mask | (1 << i), false, limit && i === up); } } if (!lead && !limit) { dp[pos][mask] = ans; } return ans; }; return dfs(i, 0, true, true); }