#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/digit-dp/special-integers-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/digit-dp/special-integers-implementation

Repovive

Special Integers - Implementation - Digit DP | Dynamic Programming | Repovive

Repovive.

Dynamic Programming21 sections · 918 units60h total

Open in Course

Special Integers - Implementation

The code

Solution:

function countSpecialNumbers(n)
    s := string(n)
    len := length of s
    dp := 4D array [len + 1][2][2][1024], all -1
    return solve
function solve
    if pos = length of s then
        return 1 if started else 0
    t := 1 if tight else 0
    st := 1 if started else 0
    if dp[pos][t][st][mask] ≠ -1 then
        return dp[pos][t][st][mask]
    limit := s[pos] if tight else 9
    count := 0
    for d from 0 to limit
        if started and (mask & (1 << d)) ≠ 0 then
            continue
        if not started and d = 0 then
            count := count + solve
        else
            newMask := mask | (1 << d)
            newTight := tight and (d = limit)
            count := count + solve
    dp[pos][t][st][mask] := count
    return count

Time: $O(\log n \cdot 2^{10})$ . Space: $O(\log n \cdot 2^{10})$ .

Time: $O(\log N \cdot 2^{10})$ . Space: $O(\log N)$ .