Find kth character in the string after nth iteration.

+2 votes
asked in Interview Question by kumar
edited by kumar

Given a binary string (e.g. 01, 101, 011), in each iteration 0 becomes 01 and 1 becomes 10, find kth character in the string after nth iteration.
Example : Given string is 1011
find 5th character/digit after two iterations.
First Iteration(0 becomes 01 and 1 becomes 10):  10011010 
Second Iteration(0 becomes 01 and 1 becomes 10): 1001011010011001

So 5th character in 1001011010011001 is 0

Add question to:

1 Answer

+2 votes
answered by admin
 
Best answer

Note: Here I am taking string  having base index 1 not 0.

Think about the the position of the ith character in next iterartion.
It will be at 2*(i-1) + 1 th carachter.
And one more pattern that character at even position i is always apposite to the character at i-1th.

Use these two logic to formulate a O(logk) solution.
I am assuming that all inputs are valid combination.And leaving some corner cases.If you find that case please mention.

 

#include<iostream>
using namespace std;

char  findDigit(char * s ,int n, int l , int k){
	
	if(n==0)
	return s[k-1];
	
	if(k%2!=0)
	  return  findDigit(s,n-1,l,((k-1)/2)+1);
    else
      return (findDigit(s,n-1,l,((k-2)/2)+1)=='0')?'1':'0';

}



int main(){
	
	char s[] = "01010010111";
    // length of string
	int l = strlen(s);
	int n;
	int k;
	//Iterations and kth digit
	cin>>n>>k;
	cout<<"Character at kth position: "<<findDigit(s,n,l,k);
	
	return 0;
	
}

 

...