Embercode: AI-powered software engineer course

1. Why does the digit DP never store the answer for a state where the tight flag is true?

A tight state's count is always zero, so there is nothing worth storingA tight state is reached by only one path, the one that copies N, and its value depends on the exact bound, so it is never reusedThe cache has no slot for the tight flag, so a tight state cannot be indexedTight states count numbers above N, which the cache must never hold

2. What does the started flag record?

Whether the current digit is smaller than the matching digit of NHow many digits have been placed so farWhether a non-zero digit has been placed yet, so leading zeros are skippedWhether the last digit placed equals the digit before it

3. What does this program print? ``

python
digits = [int(c) for c in str(121)]
print(digits)

``

[2, 1][1, 2, 1][121][0, 1, 2, 1]

4. What does this program print? ``

python
def good(x):
    s = str(x)
    for i in range(1, len(s)):
        if s[i] == s[i - 1]:
            return False
    return True


count = 0
for x in range(1, 122):
    if good(x):
        count += 1
print(count)

``

90110101121

5. For the neighbour rule, a list cache is indexed by position, by prev + 1 (11 values, since prev runs from -1 to 9), and by the started flag (2 values), as Exercise 5 suggests. For N = 3000, which has 4 digits, how many slots does the cache have in total?

Type a number.

Digit DP