Find k-th character in string

Question

Given a decimal number m. Convert it into a binary string and apply n iterations, in each iteration 0 becomes 01, and 1 becomes 10. Find the kth (1-indexing) character in the string after nth iteration.

Example 1:

Input: m = 5, n = 2, k = 5 output: 0 Explanation: Binary represntation of m is "101", after one iteration binary reprentation will be "100110", and after second iteration binary repreentation will be "100101101001".

Here is my code:

class Solution
 {
    char kthCharacter(int m, int n, int k) 
{
   
        String s1=Integer.toBinaryString(m);
    
          String str1="";
         for(int j=0;j<n;j++)
            {
                str1="";
            for(int i=0;i<s1.length();i++)
            {
            if(s1.charAt(i)=='0' && s1.charAt(i)!='1')
            {
                str1=str1+"01";
            }
            else
            {
                str1=str1+"10";
            }
          }
            s1=str1;
        }
        
      
       // System.out.println(str1);
         return str1.charAt(k-1);
      
    }
}

When I compile I get the output, upon submission of code, I get the error as ava.lang.StringIndexOutOfBoundsException. Please help to check this.

Note, that each symbol either `0` or `1` creates `2 ^ n` symbols; so the length of the final string will be `Integer.toBinaryString(m).length * (1 << n)` which can well be *out of memory* — Dmitry Bychenko, May 08 '21 at 22:35

WJS · Accepted Answer · 2021-05-09T01:34:22.927

A couple observations which may help. The first isn't critical but I point it out anyway.

if the character at i is 0 then it can't be 1 so no need to do the second check. So eliminate the condition following &&. This will help to improve performance somewhat by eliminating an unnecessary test. But keep your following else clause to properly append the desired replacement string.

     if(s1.charAt(i)=='0' && s1.charAt(i) !='1')
     
     }

And consider that you only want the kth bit which would be index k-1. So once the bit string length exceeds k, you only need the first k bits. So do the following at the end of the loop. This will ensure that you have only k bits of information. The other is extraneous.

int z = Math.min(k, str1.length());
s1 = str1.substring(0, z);

This will ensure you don't use up any more heap space than necessary.

Finally, there's no apparent guarantee that the resultant string will have the final length of at least k. So it may be necessary to check its length and take some appropriate action before attempting to access the bit at k-1.

Find k-th character in string

1 Answers1