Number

Count

Numbers At Most N Given Digit Set

public int atMostNGivenDigitSet(String[] digits, int n) {
    String s = Integer.toString(n);
    int nLength = s.length(), m = digits.length, count = 0;

    // counts integers whose digit count < nLength
    // e.g. n = 2563, digits = {1, 2, 6}
    // count == 3^1 + 3^2 + 3^3;
    for (int i = 1; i < nLength; i++) {
        count += Math.pow(m, i);
    }

    // from left to right
    for (int i = 0; i < nLength; i++) {
        boolean hasSameDigit = false;
        for (String d : digits) {
            if (d.charAt(0) < s.charAt(i)) {
                // counts integers starting with d
                count += Math.pow(m, nLength - i - 1);
            } else if (d.charAt(0) == s.charAt(i)) {
                hasSameDigit = true;
            }
        }

        // if the i-th digit of n is the same as a digit from digits
        // keeps looping
        // otherwise returns
        if (!hasSameDigit) {
            return count;
        }
    }

    // n can be constructed by digits, adds one
    return count + 1;
}

Iteration per Digit

Digit Count in Range

public int atMostNGivenDigitSet(String[] digits, int n) {
    String s = Integer.toString(n);
    int nLength = s.length(), m = digits.length, count = 0;

    // counts integers whose digit count < nLength
    // e.g. n = 2563, digits = {1, 2, 6}
    // count == 3^1 + 3^2 + 3^3;
    for (int i = 1; i < nLength; i++) {
        count += Math.pow(m, i);
    }

    // from left to right
    for (int i = 0; i < nLength; i++) {
        boolean hasSameDigit = false;
        for (String d : digits) {
            if (d.charAt(0) < s.charAt(i)) {
                // counts integers starting with d
                count += Math.pow(m, nLength - i - 1);
            } else if (d.charAt(0) == s.charAt(i)) {
                hasSameDigit = true;
            }
        }

        // if the i-th digit of n is the same as a digit from digits
        // keeps looping
        // otherwise returns
        if (!hasSameDigit) {
            return count;
        }
    }

    // n can be constructed by digits, adds one
    return count + 1;
}

Factor

Preimage Size of Factorial Zeroes Function

Binary Search:

public int preimageSizeFZF(int k) {
    // x / 5 <= f(x) <= x
    long low = k, high = 5l * k + 1;
    while (low < high) {
        long mid = (low + high) >>> 1;
        long count = f(mid);

        // for each valid k, there will be exactly 5 integers x such that f(x) == k,
        // because if x is a multiple of 5, then x + 1, x + 2, x + 3, x + 4 will have no factor of 5
        if (count == k) {
            return 5;
        }

        if (count >= k) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    return 0;
}

// = sum(the number of factor 5 in each integer)
// f(x) is non-decreasing
public long f(long x) {
    if (x == 0) {
        return 0;
    }

    return x / 5 + f(x / 5);
}

private static final int MAX_POWER = 13; // 5 ^ 13 > 10 ^ 9

public int preimageSizeFZF(int k) {
    // x = a0 * 5 ^ 0 + a1 * 5 ^ 1 + a2 * 5 ^ 2 + ...
    // f(x) = x / 5 + x / 5 ^ 2 + x / 5 ^ 3 + ...
    //      = a1 * 1 + a2 * (1 + 5) + a3 * (1 + 5 + 5 ^ 2) + ...
    //      = a1 * sum[0] + a2 * sum[1] + a3 * sum[2] + ...
    int[] sum = new int[MAX_POWER];
    Arrays.fill(sum, 1);

    for (int i = 1; i < MAX_POWER; i++) {
        sum[i] = sum[i - 1] * 5 + 1;
    }

    for (int i = MAX_POWER - 1; i >= 0; i--) {
        // the i-th coefficient is 0
        if (k / sum[i] == 5) {
            return 0;
        }
        k %= sum[i];
    }
    return 5;
}

Iterative:

public int preimageSizeFZF(int k) {
    int last = 1;
    while (last < k) {
        last = last * 5 + 1;
    }

    while (last > 1) {
        k %= last;
        if (last - 1 == k) {
            return 0;
        }
        last = (last - 1) / 5;
    }
    return 5;
}

Sqaure

Maximum Element-Sum of a Complete Subset of Indices

long long maximumSum(vector<int>& nums) {
    int n = nums.size();
    long long res = 0;
    for (int r = 1; r <= n; r++)
    {
        // Each element in the complete subset is a square number except `r`
        for (long long sum = 0, idx = 1; r * idx * idx <= n; idx++)
        {
            res = max(res, sum += nums[r * idx * idx - 1]);
        }
    }
    return res;
}