Find the nth character of an increasing sequence-CodePudding

Recently i saw a competitive coding question, the bruteforce approach doesn't meet the time complexity, Is there any other solution for this,

Question:

An expanding sequence is give which starts with 'a',we should replace each character in the following way,

a=>ab

b=>cd

c=>cd

d=>ab

there for it will look like this in each iteration,

abcd

abcdcdab

abcdcdabcdababcd

....... a number n will be given as input ,the function should return the character at nth postion.

I have tried the brute force approach by forming the full string and returning the char at n.but time limit exceeded.

i have tried the following:

dictionary={
    'a':'ab',
    'b':'cd',
    'c':'cd',
    'd':'ab'
}

string="a"

n=128
while len(string)<n:
    new_string=''
    for i in string:
        new_string =dictionary[i]
    string=new_string
print(string[n-1])

CodePudding user response：

The solution to problems like this is never to actually generate all the strings.

Here's a fast solution that descends directly through the tree of substitutions:

dictionary={
    'a':['a','b'],
    'b':['c','d'],
    'c':['c','d'],
    'd':['a','b']
}

def nth_char(n):
    # Determine how many levels of substitution are reqired
    # to produce the nth character.
    # Remember the size of the last level
    levels = 1
    totalchars = 1
    lastlevelsize = 1
    while totalchars < n:
        levels  = 1
        lastlevelsize *= 2
        totalchars  = lastlevelsize
        
    # position of the target char in the last level
    pos = (n-1) - (totalchars - lastlevelsize)
    
    # start at char 1, and find the path to the target char
    # through the levels
    current = 'a'
    while levels > 1:
        levels -= 1
        # next iteration, we'll go to the left or right subtree
        totalchars -= lastlevelsize
        # half of the last level size is the last level size in the next iteration
        lastlevelsize = lastlevelsize//2
        # is the target char a child of the left or right subtitution product?
        # each corresponds to a contiguous part of the last level
        if pos < lastlevelsize:
            #left - take the left part of the last level
            current = dictionary[current][0]
        else:
            #right - take the right part of the last level
            current = dictionary[current][1]
            pos -= lastlevelsize

    return current
    
print(nth_char(17))