Algorithm

Self Descriptive Number

Nicholas Wong

Nicholas Wong

— 2 min read
Self Descriptive Number

Question

A self-descriptive number is an integer n in given base b is b digits long in which each digit at position p (the most significant digit being at position 0 and the least significant at position b – 1) counts how many times a digit p is in n.

For example in base 10, 6210001000 is a self descriptive number.

It is 10 digit number in base 10.
It has 6 at the position 0 and there are six 0s in 6210001000.
It has 2 at the position 1 and there are two 1s in 6210001000.
It has 1 at the position 2 and there is one 2s in 6210001000.
It has 0 at the position 3 and there are zero 3s in 6210001000.
It has 0 at the position 4 and there are zero 4s in 6210001000.
It has 0 at the position 5 and there are zero 5s in 6210001000.
It has 1 at the position 6 and there is one 6 in 6210001000.
It has 0 at the position 7 and there are zero 7s in 6210001000.
It has 0 at the position 8 and there are zero 8s in 6210001000.
It has 0 at the position 9 and there are zero 9s in 6210001000.

More examples: 1210, 2020, 21200, 3211000

Construct a program to print all self-descriptive numbers below 100000000. You can ignore one fact about the self-descriptive number that it should have as many number of digits as much the base is given.

Solution

1 . Firstly all the digits get extracted from the outer loop and are stored in a variable b in each iteration.
2 . Then in the inner loop there is a count on how many times number i (this i is ith index of outer loop) is present in the string.
3 . Finally that count is compared with the digit present at the ith index stored in variable b.

Code

def is_self_descriptive_number(num):
    
    string = str(num) # convert the integer from num to string
    
    for i in range(len(string)):
        
        digit_value = ord(string[i]) - ord('0')
        count = 0 # count how many times the particular digit occur
        
        for j in range(len(string)):
            digit_value_2 = ord(string[j]) - ord('0')
            if (digit_value_2 == i): # check if it matches the digit position
                count += 1
                
        if (count != digit_value):
            return False
    
    return True
 
for i in range(10000000):
    if (is_self_descriptive_number(i)): print(i)
        
print 'done'

Reference

Read more