Find the character

Moderate
0/80
0 upvote
Asked in companies
UberCaterpillar Inc

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
AB
CD
7
ABC
A
10
Sample Output 1:
A
B
Explanation of sample input 1:
For the first test case,
The formed string will be “ABCDCDABABABCDCDCDCD…...”.
The 7th  character is A. Hence, the answer is A.

For the second test case:
The formed string will be “ABCAAABCABCABCAAAA……..” .
The 10th character is B. Hence, the answer is B.
Sample Input 2:
2
ABCDD
F
6
ACE
X
3
Sample Output 2:
F  
E
Hint

Try to maintain the size of the formed string.

Approaches (2)
Brute Force

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)].
Time Complexity

O(√K ), where ‘K’ is the position of the character.

 

In the worst case, if the size of strings ‘A’ and ‘B’ is one. The size of the formed string will be like 1+2+3+4….. which is equal to i*(i+1)/2 = ‘K’.So we will be iterating for i of order √K.Hence the overall time complexity is O(√K ).

Space Complexity

O(1).

 

In this approach, we have used constant space. Hence the overall space complexity is O(1).

Code Solution
(100% EXP penalty)
Find the character
Full screen
Console