Last Updated: 16 Sep, 2021
Find the character
Moderate
Asked in companies
Two strings ‘A’ and ‘B’ are given. A string ‘C’ has to be formed using these two strings according to the following rules:
1. Append string ‘A’ to C one time.
2. Append string ‘B’ to C two times.
3. Append string ‘A’ to C three times.
4. Append string ‘B’ to C four times.
5. Append string ‘A’ to C five times.
And so on….
Your task is to return the ‘K’th character to the newly formed string ‘C’.
For Example
If ‘A’ = “AB” and B = “CD” and K = 7.
The formed string will be “ABCDCDABABAB…...”.
So, the 7th character is A.
Input Format:
The first line of the input contains an integer, 'T,’ denoting the number of test cases.
The first line of each test case contains two strings, 'A’ and ’B’.
The second line contains ‘K’ representing the character number to be found.
Output Format:
For each test case, print a character denoting the ‘K’th character.
Print the output of each test case in a separate line.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= length of ‘A’,length of ‘B’ <= 100.
1 <= ‘K’ <= 10^15
Time limit: 1 sec
Approaches
In this approach, we will first declare a string ‘STRING_SIZE’ to store the size of the newly formed string.
Now, we will update the ‘STRING_SIZE’ according to the given conditions until ‘STR’ is less than ‘K’. After that, we will check if the last inserted strings are strings ‘A’ or ‘B’.We will find the number of extra added characters as ‘EXTRA’.
We will now remove the extra strings and decrease ‘EXTRA’. Now the ‘EXTRA’ + 1th character from the last of the last inserted string is the ‘K’th character of the formed string.
Algorithm:
- Declare the 'STRING_SIZE' integer.
- Set 'STRING_SIZE' as 0.
- Set i =0
- While the length of ‘STR’ is less than ‘K’, do the following:
- Increment i to i+1.
- If i is odd, set 'STRING_SIZE' as 'STRING_SIZE' + (i * length of ‘A’).
- If i is even, set 'STRING_SIZE' as 'STRING_SIZE' + (i * length of ‘B’).
- Set ‘EXTRA’ as 'STRING_SIZE' - ‘K’.
- If i is odd:
- Set ‘EXTRA’ as ‘EXTRA’ % length of ‘A’.
- Return A[length of ‘A’ - (‘EXTRA’ + 1)].
- If i is even:
- Set ‘EXTRA’ as ‘EXTRA’ % length of ‘B’.
- Return B[length of ‘B’ - (‘EXTRA’ + 1)].
In the previous approach, we iterated ‘i’ from 1 to √K to make the string.
In this approach, we will run a binary search over this range and will find the smallest ‘i’ for which the 'STRING_SIZE' is greater than or equal to ‘K’.We will find the number of extra added characters as ‘EXTRA’.
We will now remove the extra strings and decrease ‘EXTRA’. Now the ‘EXTRA’ + 1th character from the last of the last inserted string is the ‘K’th character of the formed string.
Algorithm:
- Set ‘L’ as 1.
- Set ‘R’ as √(2*K) + 1.
- Declare ‘i’’.
- Declare ‘ANS’ to store the smallest ‘i’ for which length of the string is greater than or equal to ‘K’.
- Declare ‘ANS_SIZE’ to store the stringsize corresponding to ‘ANS’.
- While ‘L’ is less than or equal to ‘R’, do the following:
- Set ‘i’ as (‘L’ + ‘R’) /2.
- Set ‘ODD’ as ‘i’/2. (Number of odd numbers from 1 to ‘i’).
- Set ‘EVEN’ as ‘i’/2. (Number of even numbers from 1 to ‘i’).
- If ‘i’ % 2 == 1,set ‘ODD’ as ‘ODD‘ + 1.
- Set 'STRING_SIZE' as 0.
- Set 'STRING_SIZE' as 'STRING_SIZE' + (length of ‘A’ * ‘ODD’ * ‘ODD’) (N2 is the sum of first N odd numbers.)
- Set 'STRING_SIZE' as 'STRING_SIZE' + (length of ‘B’ * ‘EVEN’ * (‘EVEN’ + 1) ) ( N*(N+1) is the sum of first N even numbers.)
- If 'STRING_SIZE'is greater than or equal to ‘K’, do the following:
- Set ‘ANS’ as ‘i’.
- Set ‘ANS_SIZE’ as 'STRING_SIZE'.
- Set ‘R’ as ‘i’ - 1.
- Else:
- Set ‘L’ as ‘i’ + 1.
- Set ‘L’ as ‘i’ + 1.
- Set ‘EXTRA’ as ‘ANS_SIZE’ - ‘K’.
- If ‘ANS’ is odd:
- Set ‘EXTRA’ as ‘EXTRA’ % length of ‘A’.
- Return A[length of ‘A’ - (‘EXTRA’ + 1)].
- If ‘ANS’ is even:
- Set ‘EXTRA’ as ‘EXTRA’ % length of ‘B’.
- Return B[length of ‘B’ - (‘EXTRA’ + 1)].
Similar problems