Binary string play

code_dominar 0
Viewed 83

Problem :

We are given a series of Binary Strings. The first term in this series is 0. Hence, T1 = '0'. To find the string at any given Ti, we look at Ti - 1 and replace all occurances of '0' with '01' and '1' with '10'. You are given two integers N and X, your job is to find TN and return its Xth index. Note: Ti are 1-indexed.

Input Format:

First line of input contains an integer T, representing the number of test cases. The next T lines contains two space separated integers, N and X.

Output Format:

Print the Xth index in Nth row

Sample Input:

1
4 5

Sample Output:

1

Explanation:

T1: '0'
T2: '01'
T3: '0110'
T4: '01101001'

The 5th element in T4 is '1'.

I tried below solution but getting time limit exceed for n value greater than 25.how to handle large test cases ?

from sys import stdin , setrecursionlimit
setrecursionlimit(10**8)
t = int(input())

def temp(s,n):
    if n==0:
        return s
    ans = ''
    d = {
        '0':'01',
        '1':'10'
    }
    for ele in s:
        ans+=d[ele]
        
    return temp(ans,n-1)
   
while t:
    n,x = [int(x) for x in stdin.readline().strip().split()] 
    s = '0'
    res = temp(s,n)
    print(res[x-1])
    
    t-=1
string list recursion binary python
3 Answers

Try this. You can use iteration (for loop) rather than recursion:

# Iterative function to get T(i)
def T(i): # Define function
    l = '0' # Variable that holds the last value in the sequence
    for _ in range(i-1): # Iterate i-1 times
        d = {'0': '01', '1': '10'} # Just like in your code
        l = ''.join(map(d.get, l)) # Equivalent to ''.join(d[c] for c in l)
    return l # Return the last value

r = int(input()) # Number of test cases
while r: # Just like in your code
    n, x = map(int, input().split()) # Get n and x as input, and convert to integer
    print(T(n)[x-1]) # Get T(n) and get the xth index
    r -= 1 # Decrement r by 1

Input:

1
4 5

Output:

1
The Thonnu0

There is a pattern for the elements generated.

0
01
0110
01101001
0110100110010110
01101001100101101001011001101001
0110100110010110100101100110100110010110011010010110100110010110

That pattern is nextElement is previousElement + flipallbits(previousElement). And try to form a recurrence relation to find the bit in a particular index.

So say if an index say 4, its the flipped operation of index 0.

Say if an index say 5, its the flipped operation of index 1. which inturn is a flipped operation of index 0.

So you have remove the highest power of 2 from the index and then flip the bit and if index is 0 return 0.

x = 3
def findElement(x):
    if(x == 0):
        return False
    power = 1
    while (power*2) <= x:
        power *= 2
    return not findElement(x - power)
print(int(findElement(x)))

There is no need for n in this implementation. Another option is just count, the number of ones in the binary representation of index x and the check if its even. if its even return 0 else 1.

Albin Paul0

you just need to see the pattern, where for odd to even number transiiton it is just previous string + reverse of it whereas for even to odd transition it is previous string + complement of value of previous string

here is code

def function(n, x):
    tmp = ['0']
    if n==0:
        if x>len(tmp)-1:
            return -1
        elif x<=len(tmp)-1:
            return tmp[x]
    for i in range(1, n):
        if not i%2:
            tmp = tmp + tmp[::-1]
        else:
            tmp = tmp + ['0' if i=='1' else '1' for i in tmp]
    if x<=len(tmp)-1:
        return tmp[x]
    return -1

-1 if index out of range.

sahasrara620
Related