CareerCup

This problem can be of two type :
First : all integer in given input are lies between 0 to 9.
Here is the algo :

- In first pass to input string, find the sum of all integer by testing each char by isnum(), and summing integer value into sum variable.
  - Now we keep one pointer at sum and another the end of input string, we find integer and char and populate it at first pointer. move second by 2 and first by the value of integer, 
  - keep going with this process.

2nd : the integer might have value greater then 9.
Here is the algo :

- We use atoi() function along with isalpha() to calculate output string length, 
      -- Isalpha() is to find weather we reach to next integer from last one,
      -- Atoi() is to find current integer before next char.
   For example : current input is 110f10g
   then Isalpha give false, and atoi() give 110, then by the help of isalpha we move our next pointer on input string.
  - we apply same concept while outputting.

Actually I forget to write one more thing and is applied to both the algo, which is "compression", We compress the string first, in first move along with length calculation, for example

if input is a1b1c2 then after first step string will be abc2 with length 4
 if input is a2b1c1d5e1f4g0h1i5 then after first step it will be a2bcd5ef4hi5 with length 20. then we apply the same.
this step also require O(input length) time

complexity : O(length of output string)

Approach: shift elements to make enough space for copying.

This is o(n2) problem

my algo tested and working

static char[] alphabets = { 'a', 'b', 'c', 'd', 'e', 'f', 'g' };
        static void Main(string[] args)
        {
            string input = "a2b3c4d2";
            char[] inputArray = input.ToArray();
            int sum = 0;

            Func<char,bool> IsChar = delegate(char ch)
            {
                return Program.alphabets.Contains(ch);
            };

            for (int i = 0; i < inputArray.Length; i++)
            {
                var item = inputArray[i];
                if (!IsChar(item))
                {
                    var incr = Int32.Parse(inputArray[i].ToString()) - 2;
                    sum += incr;
                }
            }

            Console.WriteLine("sum is " + sum);
            Array.Resize(ref inputArray, inputArray.Length + sum);
            Console.WriteLine("new array size is " + inputArray.Length);

            for (int i = 0; i < inputArray.Length; i++)
            {
                var previousChar = char.MinValue;

                var item = inputArray[i];
                if (!IsChar(item))
                {
                    previousChar = inputArray[i - 1];
                    int positions = Int32.Parse(inputArray[i].ToString());

                    char[] newarray = new char[19];


                    for (int i1 = inputArray.Length-1; i1 >i ; i1--)
                    {
                        if (inputArray[i1] != '\0')
                        {
                            inputArray[i1 + positions-2] = inputArray[i1];
                        }
                    }

                    for (int i2 = 0; i2 <=  positions-2; i2++)
                    {
                        inputArray[i++] = previousChar;
                    }
                   
                }
            }

            foreach (var it in inputArray)
            {
                Console.Write(it + " ");
            }
        }

It is possible to do it in place, using a small buffer to handle overflows.
I assumed that the input array is already resized to the final size and free space is filled by '\0' as it mentioned in the question. however finding the final size is easy and others talked about it.
(the tricky part is how to fill the array in place)

static void fillArray(char[] str)
        {
            Queue<char> buffer = new Queue<char>();
            int p1 = str.Length - 1;
            int p2 = p1;
            char prechar;
            
            while (str[p2] == '\0') { p2--; }

            while (true)
            {
                int repeat;
                if (buffer.Count > 0)
                {
                    repeat = int.Parse(buffer.Dequeue().ToString());
                }
                else
                {
                    repeat = int.Parse(str[p2].ToString());
                    p2--;
                }
                if (buffer.Count > 0)
                {
                    prechar = buffer.Dequeue();
                }
                else
                {
                    prechar = str[p2];
                    p2--;
                }
                
                for (int i = p1; i > p1 - repeat; i--)
                {
                    if (i == p2)
                    {
                        buffer.Enqueue(str[i]);
                        p2--;
                    }
                    str[i] = prechar;
                }
                p1 = p1 - repeat;
                if (p2 < 0 && buffer.Count == 0) break;
            }

        }

Lets start from the end. This way we can easily do it without shifts.

Find sum of all the numbers ... which would be the size of o/p array

Now start from array+size and come backwards by filling all the elements ....

i/p array = a1b2
size = 1+2 = 3

array+(size-1) = b
array+(size-2) = b
array+(size-3) = a

Here is my C# implementation. To convert it to java or c is trivial...

1using System;
using System.Text;

namespace Algo
{
    static class Parser
    {
        //input a2b1c3d10
        //output aabcccdddddddddd...
        public static String Parse(String str)
        {
            if (String.IsNullOrEmpty(str))
                return String.Empty;

            StringBuilder sb = new StringBuilder();
            char[] strArr = str.ToCharArray();
            int counter = 0;
            while (counter < strArr.Length)
            {
                if(isChar(strArr[counter]))
                {
                    char c = strArr[counter];
                    ++counter;
                    string sNumberofTimes = strArr[counter].ToString(); 
                    
                    while(isNumber(strArr[counter]))
                    {
                        sNumberofTimes +=strArr[counter].ToString();
                        counter++;
                    }

                    int numberOfTimes = int.Parse(sNumberofTimes);
                    for (int i = 0; i < numberOfTimes; i++)
                    {
                        sb.Append(c);
                    }
                }
                //Console.WriteLine(strArr[counter]);
                counter++;
            }
            return sb.ToString();
        }

        private static bool isChar(char c)
        {
            char[] possibleChars = { 'a', 'b', 'c', 'd' };
            for (int i = 0; i < possibleChars.Length; i++)
            {
                if (c == possibleChars[i])
                    return true;
            }
            return false;
        }

        private static bool isNumber(char c)
        {
            int[] possibleNumbers = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
            for (int i = 0; i < possibleNumbers.Length; i++)
            {
                if (c == possibleNumbers[i])
                    return true;
            }
            return false;
        }
    }
}

It makes quite a time to find out the algorithm.
1> In the begging of the processing, if the decode will result in shrinking or the space in the left is enough to contain the expansion, do it using two pointers, one write and one read.
2> Once you got a word pair you can not expand to the left, which means your write pointer will collide your read pointer, the algorithm change to second stage, it will start to counting the number of the extra space on the right until it reach the end of the array or the extra space needed is zero. After you got this, you decode your char array using another two pointers, this time write pointer is bigger than read pointer until.
3> Goto 1> if there are still some bytes left.

#include <stdio.h>

void chardecode(char* pInput, 
                unsigned int len,
                unsigned int prefix,
                unsigned int second)
{
  char  *pTemp, *pTemp2;
  unsigned int shrinked;
  int count,count2, count3;
  if(NULL==pInput)
    return;
  //First round shrink here
  printf("prefix is %d second is %d len %d for %s\n", prefix, second, len, pInput);
  if(second)
  {
    //that means we are in the second state of the algorithm
    //we try to find the first zero expand area
    pTemp=pInput;
    pTemp2=pTemp;
    for(count=-prefix, count2=0;count2<len;count2++)
    {
      pTemp++;
      if(*pTemp>'0' && *pTemp<='9')
      {
        count+=*pTemp-'2';
        if(count==0)
        {
          count2++;
          break;
        }
      }else
      {
        return;
      }
      pTemp++;
    }
    //Here we are doing the normal expand
    printf("count is %d count2 is %d\n", count, count2);
    pTemp=pInput+(count2<<1)-2;
    pTemp2=pTemp+count+1;
    pInput=pTemp2+1;
    len=len-count2;

    for(;count2;count2--)
    {
      for(count=*(pTemp+1)-'0';count;count--)
      {
        *pTemp2=*pTemp;
        pTemp2--;
      }
      pTemp-=2;
    }
    //now we are going to perform the left part if existed;
    printf("len is %d\n", len);
    if(!len)
    {
      *pInput='\0';
      return;
    }
  }
    
  pTemp=pInput;
  pTemp2=pTemp;
  for(count=0, count2=0, shrinked=0;count2<len;count2++)
    {
      pTemp++;

      if(*pTemp>'0' && *pTemp<='9')
      {
        count+=*pTemp-'2';
        if(count<=0)
        {
          shrinked=1;
          for(count3=*pTemp-'0';count3;count3--)
          {
            *pTemp2++=*(pTemp-1);
          }
        }else
        {
          //in this case we enter the state mahine second state:
          {
            //we found that we are in the middle of the array 
            //and we can not shrink anymore
            chardecode(pTemp-1, len-count2, *pTemp-'2'-count, 1);
            return;
          }
        }
      }else
      {
        return;
      }
      pTemp++;
    }
  *pTemp2='\0';
}


int main()
{
    char  p[]="a1b1c1";
    char  p2[]="a2b2c2";
    char  p3[]="a3b4     ";
    char  p4[256]="a1b4c4d1e5f4";
    
    chardecode(p, 3, 0,0);
    printf("p is %s\n", p);
    chardecode(p2,3, 0, 0);
    chardecode(p3, 2,0,0);
    printf("p2 is %s\n", p2);
    printf("p3 is %s\n", p3);
    printf("p4 is %s\n", p4);
    chardecode(p4,6, 0,0);
    printf("p4 is %s\n", p4);
}

for(int i=1;i<n-1;i=i+2)
{
if(a[i]==1)
{
p=a[i];
kew=kew+p;
m=a[--i];
}
elseif(a[i]==3)
{
q=a[i];
kew=kew+q;
n=a[--i];
}
elseif(a[i]==5)
{
r=a[i];
kew=kew+r;
z=a[--i];
}
}
char a=new array[kew];
int index=0;
for(i=0;i<p;i++)
{
a[index]=m;
index++;
}
for(i=0;i<q;i++)
{
a[index]=n;
index++;
}
for(i=0;i<r;i++)
{
a[index]=z;
if(index<(kew-1))
index++;
}

Here's the in-place solution in Python, with tests. It's done in constant space. There's no recursion and the array never grows larger than the final result.

def test():
    test_strings = [
        ('a1b1c1', 'abc'),
        ('a1b3c5', 'abbbccccc'),
        ('a5b3c1', 'aaaaabbbc'),
        ('a5b5c5', 'aaaaabbbbbccccc'),
    ]
    for s, expected_result in test_strings:
        # strings are immutable in Python, so make this a list
        lst = list(s)
        expand(lst)
        assert expected_result == ''.join(lst)

def expand(a):
    # i = input index
    # j = output index
    # In our first pass, we compress the 1s
    # and compute how much space we'll have.
    i = 0
    j = 0
    new_len = 0
    while i < len(a):
        c = a[i]
        cnt = int(a[i+1])
        new_len += cnt
        i += 2
        a[j] = c
        j += 1
        if cnt > 1:
            a[j] = str(cnt)
            j += 1
    # Set the array to correct length.
    while len(a) > new_len:
        a.pop()
    # Note that this is the only place we append
    # to the list.  Everything is in-place, and we
    # have constant storage for the locals: i, j, cnt, new_len.
    while len(a) < new_len:
        a.append(None) 
    # In the second pass, we work backward through
    # the string and write out the final result.  By
    # working backward, we know we'll have room.
    i = j - 1 # last element in compress string
    j = new_len - 1 # where we write
    while i >= 0:
        c = a[i]
        i -= 1
        try:
            cnt = int(c)
            c = a[i]
            i -= 1
        except:
            cnt = 1
        while cnt > 0:
            a[j] = c
            j -= 1
            cnt -= 1

test()

void ExpandStr(char* str)
{
        size_t len = strlen(str) + 1;
        // count ints
        size_t count = 0;
        size_t sum = 0;
        for (size_t i=0; i<len-1; i++) {
                if (str[i] >= '1' and str[i] <= '9') {
                        count++;
                        sum += (size_t (str[i] - '0')) -1;
                }

        }

        size_t finalLen = len + sum - count;
        size_t currentIdx = finalLen - 1;
        str[finalLen] = '\0';
        for (size_t i=len-1; i>0; i--){
                if (str[i] >= '1' and str[i] <= '9') {
                        size_t cnt = (size_t(str[i] - '0')) - 1;
                        char c = str[i-1];
                        while (cnt != 0) {
                                str[currentIdx--] = c;
                                cnt--;
                        }
                } else {
                        str[currentIdx--] = str[i];
                }
        }
}

Here is a straightforward solution :

Shift all the elements to the end of the array and then trace the part where the info is. keep the read char in temp char and keep the number that comes after in temp amount. Then in a loop add the amount of chars starting from the beginning of the array. Do that until you read and processed all the chars. Keep a global counter so you know where you left when proicessing for the next character ..

Working solution in java.
I am assuming the entire array is passed,and the end elements are filled with spaces
I calculate the number of pairs,and I start at the last pair and work my way to the first pair

public static void main(String[] args) {
	//	new ProgramToCompressString().displayCompressedString("ABD");
		new ProgramToCompressString().displayDecompressedString(new char[]{'a','2','b','3','d','3',' ',' '});
	}

	private void displayDecompressedString(char[] cs) {
		System.out.println("Before : "+Arrays.toString(cs));
		int f = 0 ;
		while(cs[f] != ' '){
			f = f+1;
		}
		
		int pairs = f/2;
		assert f%2==0;
		
		System.out.println("Number of pairs : "+ pairs);
		
		int rptCount = 0 ;
		
		for(int i=pairs; i> 0 ; i --){
			char temp  = cs[i*2-2];
			int rpt = Character.getNumericValue(cs[i*2-1]);
			rptCount += rpt;
			for(int j = 0 ; j < rpt ; j ++){
				System.out.println(rpt+" "+j);
				cs[cs.length-rptCount+j] = temp;
			}
		}
		
		System.out.println("After : "+Arrays.toString(cs));
	}

All test cases provided by author succeeds.

public static void expand(char[] chars) {
		int currPtr = 0;
		while (currPtr < chars.length && chars[currPtr] != 0) {
			if (Character.isDigit(chars[currPtr])) {
				int tmp = currPtr;
				StringBuilder sb = new StringBuilder();
				while (tmp<chars.length && Character.isDigit(chars[tmp])) {
					sb.append(chars[tmp]);
					tmp++;
				}
				int shift = Integer.parseInt(sb.toString());
				char c = chars[currPtr - 1];
				if (shift == 1) {
					tmp = currPtr;
					while (chars[tmp] != 0 && tmp < chars.length - 1) {
						chars[tmp] = chars[tmp + 1];
						tmp++;
					}
					chars[tmp] = 0;
				} else {
					tmp = currPtr + String.valueOf(shift).length();
					shift -= 2;
					// shift right 'shift' position, make room
					if (shift > 0) {
						shiftP(chars, tmp, shift);
					}
					for (int i = currPtr - 1; i <= currPtr + shift; i++) {
						chars[i] = c;
					}
				}
			}
			currPtr++;
		}
	}

	private static void shiftP(char[] chars, int head, int shift) {
		int ptr = 0;
		while (chars[ptr] != 0) {
			ptr++;
		}
		ptr--;
		for (int i = ptr; i >= head; i--) {
			chars[i + shift] = chars[i];
		}
	}

var arr = ['a','1','b','2','c','3','d','1','1','','','','','','','','','','','','','',''];
var p = arr.length - 1;
for(var i=p;i>=0;i--){
	//getNumber
	var n = 0;
	var nlen = 0;
	while(arr[i] != '' && arr[i] < 'a' && i >=0){
		if(nlen>0) n+= Math.pow(10,nlen);
		else n += parseInt(arr[i]);
		arr[i]='';
		i--;
		nlen++;
	}
	if(n==0) continue;
	var c = arr[i];
	arr[i] = '';
	console.log(n);
	console.log(c);

	for(var j=0;j<n;j++){
		arr[p] = c;
		p--;
	}
	console.log(arr);
}


console.log(arr);

my code has a bug that is the space at right must be enough long...

Here's the approach.
1. calculate the length of the pattern and the required length
2. There will be two cases which we need to handle
case 1: the pattern length >= required length
e.q. a1b2 (pat length =4) , required length = 3
or a2b2 (pat length =4) , required length = 4

In this case iterate over the pattern and shrink '1' and repeat last char for '2'
case 2:
pattern length < required length
e.g. a1b2c4

a) shrink all the 1's , so a1b2c4 becomes ab2c4
b) now start filling from the back

Here's the code for the same

string decode(string estr){
	int patlen = estr.length();
	int reqdlen=0;
	for(int i=0;i<patlen;++i){
		if( isDigit(estr[i]) ){
			reqdlen+=estr[i]-'0';
		}
	}
	string ans;
	ans.resize(reqdlen);
	cout<<ans.length()<<endl;
	//case 1: if patlen >= reqdlen
	//e.g. a1 a1b2
	if( patlen  >= reqdlen ){
		int idx=0;
		char lastchar;
		for(int i=0;i<patlen;++i){
			if( isChar(estr[i]) ){
				lastchar = estr[i];
				ans[idx] = estr[i];
				//cout<<ans[idx]<<endl;
				idx++;
			}else if( estr[i] == '2' ){
				//a1b3 will never come
				//cout<<lastchar<<endl;
				ans[idx] = lastchar;
				idx++;
			}
		}
		//ans[idx]='\0';
	}else if( patlen < reqdlen ){
		//shrink the pattern by moving all chars with
		//count 1
		int idx =0;
		char lastchar;
		int newlen=0;
		for(int i=0;i<patlen;++i){
			if( isChar[estr[i]] ){
				ans[idx++] = estr[i];
			}else if( estr[i] != '1' ){
				idx++;
			}
		}

		newlen = idx;
		//now start filling from the back
		int lastdigit;
		idx=reqdlen-1;
		for(int i=newlen-1;i>=0;--i){
			if( isDigit(estr[i]))
				lastdigit=estr[i]-'0';
			else{
				for(int j=0;j<lastdigit;++j){
					ans[idx--]=estr[i];
				}
				lastdigit=1;
			}
		}
	}

	return ans;
}

O(N),first pass we just deal 1 to make the string shorter from the start to the end, second pass we deal others to make the string longer from the end to the start.

public static void main(String[] args) {
        SimpleReader in = new SimpleReader1L();
        SimpleWriter out = new SimpleWriter1L();

        String array = in.nextLine();

        int startIndex = 0;
        int endIndex = 2;
        String expandedStr = "";

        while (endIndex <= array.length()) {
            String subStr = array.substring(startIndex, endIndex);

            char alphabet = subStr.charAt(0);
            int number = Integer.parseInt(subStr.charAt(1) + "");

            int count = 0;
            while (count < number) {
                expandedStr += alphabet;
                count++;
            }
            startIndex += 2;
            endIndex += 2;
        }

        char[] newArray = expandedStr.toCharArray();

        out.println(expandedStr);
        in.close();
        out.close();

}

//give a1b2c3
	//return abbccc
	String tostring(String s){
		char [] array = new char[20];
		TreeMap<Character,Integer> map = new TreeMap<>();
		for(int i=0;i<s.length();i=i+2){
			map.put(s.charAt(i), Character.getNumericValue(s.charAt(i+1)));
		}
		int count = 0;//index to track
		for(Character c:map.keySet()){
			 for(int k=count;k<map.get(c)+count;k++){
				array[k] = c;
			 }
			 count = map.get(c)+count;
		}
		return new String(array);
	}

#include<iostream>
#include<math.h>
/*Assumptions:
 char string given in format -- char []
 number may be any positive integer
 always single alphabet, anything other than number is considered alphabet
 all inputs correct. E.g. no incorrect inputs like 22a2 or abc4-->written as a1b1c4
*/
using namespace std;

void fix(char *all_s, char *all_e, char *in_s, char *in_e)
/*
all_s,all_e : mark the start and ending of complete space under consideration
in_s,in_e : mark where to start reading from when running backwards

Alg:
Move backwards
-Get num
Mark position Pos from where to start copying later, save char to copy
Recursively call itself with new space under consideration and where to start reading input
Upon return, from Pos,copy saved character num times
*/
{
 
 if((in_s>=in_e)||(all_s>=all_e)) return;
 
 //Moving backwards get num
 int num = 0, count = -1;
 while(*in_e>='0'&&*in_e<='9') 
 {
  count++;
  num = (( *in_e- '0' ) * int(pow((double)10,(double)count))) + num;
  in_e--;
 }
 
 char *pos = all_e-num+1;
 char c = *in_e;
 
 fix(all_s,all_e-num,in_s,in_e-1);
 
 for(int i = 0; i<num; i++)
 {
  *pos = c;
  pos++;
 }
}
int main()
{
char str[] = "a2b4c5---------------------------------------------------";
cout<<"Input : "<<str;
//call properly
fix(&str[0],&str[10],&str[0],&str[5]);
cout<<"\nRESULT : "<<str;

char str2[] = "a1b1c4---------------------------------------------------";
cout<<"\nInput : "<<str2;
//call properly
fix(&str2[0],&str2[5],&str2[0],&str2[5]);
cout<<"\nRESULT : "<<str2;

char str3[] = "a11b11c5---------------------------------------------------";
cout<<"\nInput : "<<str3;
//call properly
fix(&str3[0],&str3[11+11+5-1],&str3[0],&str3[7]);
cout<<"\nRESULT : "<<str3;
return 0;
}

My algo is:
1st, traverse the string and get the total length of the result string, assuming len = N.
2nd, traverse the string from tail, and then parse and write the new string also from the tail, a[N-1].

In this solution, time complexity is O(n).

first iterate from back.First check the sum of the all numbers which is the length of the array.And in the next iteration expand the digits if the expansion is going to overwrite the string then do it at that place else do it at the right place.For the next iteration remove the spaces.--O(n)

Should be relatively easy like this:

1) Remove all "1"s by shifting chars to the left.
2) Start expanding from the end of the array to the end of the expanded array and move towards the beginning from there. Since all "1"s have been removed the space will always be enough to not overwrite characters.

void process(char* A, int delmes, char thischar, int rep){
int len = strlen(A);
for (int i = len ; i < len + rep; i++){
A[i] = thischar;
}
A[len + rep] = '\0';
for (int i = delmes; i < 2+delmes; i++){
A[i] = ' ';
}
};
void process2(char* A){
char* f = A;
char* b = A;
while (*f){

while (*b == ' '){
b++;
}
*f = *b;
f++;
b++;
}

};

void addict(){
char A[100] = "a1b1c3d4w2s4";
int len = strlen(A);
char tocopy = ' ';
int rep = 0;
for (int i = 0; i < len; i++){

if (!(i % 2)){
tocopy = A[i];
}
else {
rep = isalpha(A[i]);
process(A, i - 1, tocopy, rep);
}

}
process2(A);
cout << A;

};

java code for the input a1b2c3 and expected output is abbccc


package practice;


import java.util.Scanner;

public class a1b2c3 {

public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
System.out.println("Enter the string");
String s=sc.nextLine();
String s1="";
String s2="";
char[] c=s.toCharArray();
for(int i=0;i<c.length;i++)
{
if(i%2!=0)
{
s1=s1+c[i];
}
else
{
s2=s2+c[i];
}

}
int n=Integer.parseInt(s1);
String s3="";
int j=s2.length()-1;

while(n>0 && j<=s2.length())
{
int rem=n%10;
for (int i = rem; i >0; i--)
{
s3=s2.charAt(j)+s3;

}
j--;
n=n/10;

}
System.out.println("OUTPUT== "+s3);

}
}

java code for the input a1b2c3 and expected output is abbccc....

package practice;


import java.util.Scanner;

public class a1b2c3 {

	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		System.out.println("Enter the string");
		String s=sc.nextLine();
		String s1="";
		String s2="";
		char[] c=s.toCharArray();
		for(int i=0;i<c.length;i++)
		{
			if(i%2!=0)
			{
				s1=s1+c[i];
			}
			else
			{
				s2=s2+c[i];
			}
				
		}
		int n=Integer.parseInt(s1);
		String s3="";
		int j=s2.length()-1;
		
		while(n>0  && j<=s2.length())
		{
			int rem=n%10;
			for (int i = rem; i >0; i--) 
			{
				s3=s2.charAt(j)+s3;
				
			}
			j--;
			n=n/10;
			
		}
		System.out.println("OUTPUT== "+s3);

	}
}

Write a cprogram to print string "aabbbccddxx"
Output is 2a3b2c2d2x

package anuj_sir_java;
import java.util.*;

public class stringPractice {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String name = "a2b4c6";
		String ans = "";
		String name1 = new String("Rittu Dutta is a good boy");
		for(int i=0;i<name.length();i+=2)
		{
			char temp=name.charAt(i);
			char c= name.charAt(i+1);
			int p=Character.getNumericValue(c);
			for(int j=0;j<p;j++)
			{
				ans+=temp;
			}
		}
		
		System.out.println(ans);
		Scanner scan = new Scanner(System.in);
		System.out.println("Enter the index no:");
		int n = scan.nextInt();
		System.out.println(ans.charAt(n));

	}

}

def expandchar(s):
letters, digits = s[0::2], s[1::2]
for i in range(len(letters)):
sys.stdout.write(letters[i] * int(digits[i]))