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);
}

1012 - Numbers With Repeated Digits

1012. Complement of Base 10 Integer (Easy)

Solution 1.

All Problems

All Solutions

Welcome to Subscribe On Youtube

1012. Complement of Base 10 Integer (Easy)

Solution 1.

All Problems

All Solutions