Given two positive integers N and K, the task is to find the Kth character of a string obtained by performing the following operation on a string S( initially “A”) N times.
Every ith operation generates following string (Si):
Si = Si – 1 + ‘B’ + rev(comp(Si – 1))
where,
comp() denotes the complement of string i.e., A is changed to B and B is changed to A.
and rev() returns the reverse of a string.
Examples:
Input: N = 3, K = 1
Output: A
Explanation:
Initially, after first operation, S1 = “A”
After 2nd operation, S2 = “ABB”
After 3rd operation, S3 = “ABBBAAB”
The first character of S3 is ‘A’.
Input: N = 2, K = 3
Output: B
Approach: The idea is to use recursion to generate the new string from the previously generated string and to repeat the process until N operations are performed. Below are the steps:
- Initialize two string prev as “A” and curr as an empty string.
- If N = 1 then returns prev otherwise perform below operation.
- Iterate a loop (N – 1) times, each time update curr as prev + “B”.
- Reverse the string prev.
- Again update the string curr string as curr + prev.
- Update string prev as curr.
- After the above steps return the (K – 1)th character of the string curr.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to return Kth character// from recursive stringchar findKthChar(int n, int k){ string prev = "A"; string cur = ""; // If N is 1 then return A if (n == 1) { return 'A'; } // Iterate a loop and generate // the recursive string for (int i = 2; i <= n; i++) { // Update current string cur = prev + "B"; // Change A to B and B to A for (int i = 0; i < prev.length(); i++) { if (prev[i] == 'A') { prev[i] = 'B'; } else { prev[i] = 'A'; } } // Reverse the previous string reverse(prev.begin(), prev.end()); cur += prev; prev = cur; } // Return the kth character return cur[k - 1];}// Driver Codeint main(){ int N = 4; int K = 3; cout << findKthChar(N, K); return 0;} |
Java
// Java program for // the above approachimport java.util.*;class GFG{ // String reversestatic String reverse(String input) { char[] a = input.toCharArray(); int l, r = a.length - 1; for (l = 0; l < r; l++, r--) { char temp = a[l]; a[l] = a[r]; a[r] = temp; } return String.valueOf(a);} // Function to return Kth character// from recursive Stringstatic char findKthChar(int n, int k){ String prev = "A"; String cur = ""; // If N is 1 then return A if (n == 1) { return 'A'; } // Iterate a loop and generate // the recursive String for (int j = 2; j <= n; j++) { // Update current String cur = prev + "B"; // Change A to B and B to A for (int i = 0; i < prev.length(); i++) { if (prev.charAt(i) == 'A') { prev.replace(prev.charAt(i), 'B'); } else { prev.replace(prev.charAt(i), 'A'); } } // Reverse the previous String prev = reverse(prev); cur += prev; prev = cur; } // Return the kth character return cur.charAt(k);}// Driver Codepublic static void main(String[] args){ int N = 4; int K = 3; System.out.print(findKthChar(N, K));}}// This code is contributed by Rajput-Ji |
Python3
# Python3 program for the above approach# Function to return Kth character# from recursive stringdef findKthChar(n, k): prev = "A" cur = "" # If N is 1 then return A if (n == 1): return 'A' # Iterate a loop and generate # the recursive string for i in range(2, n + 1): # Update current string cur = prev + "B" # Change A to B and B to A temp1 = [y for y in prev] for i in range(len(prev)): if (temp1[i] == 'A'): temp1[i] = 'B' else: temp1[i] = 'A' # Reverse the previous string temp1 = temp1[::-1] prev = "".join(temp1) cur += prev prev = cur # Return the kth character return cur[k - 1]# Driver Codeif __name__ == '__main__': N = 4 K = 3 print(findKthChar(N, K))# This code is contributed by mohit kumar 29 |
C#
// C# program for // the above approachusing System;class GFG{ // String reversestatic String reverse(String input) { char[] a = input.ToCharArray(); int l, r = a.Length - 1; for (l = 0; l < r; l++, r--) { char temp = a[l]; a[l] = a[r]; a[r] = temp; } return String.Join("", a);} // Function to return Kth character// from recursive Stringstatic char findKthChar(int n, int k){ String prev = "A"; String cur = ""; // If N is 1 then return A if (n == 1) { return 'A'; } // Iterate a loop and generate // the recursive String for (int j = 2; j <= n; j++) { // Update current String cur = prev + "B"; // Change A to B and B to A for (int i = 0; i < prev.Length; i++) { if (prev[i] == 'A') { prev.Replace(prev[i], 'B'); } else { prev.Replace(prev[i], 'A'); } } // Reverse the previous String prev = reverse(prev); cur += prev; prev = cur; } // Return the kth character return cur[k];}// Driver Codepublic static void Main(String[] args){ int N = 4; int K = 3; Console.Write(findKthChar(N, K));}}// This code is contributed by Rajput-Ji |
Javascript
<script> // Javascript program for the above approach // String reverse function reverse(input) { let a = input.split(''); let l, r = a.length - 1; for (l = 0; l < r; l++, r--) { let temp = a[l]; a[l] = a[r]; a[r] = temp; } return a.join(""); } // Function to return Kth character // from recursive String function findKthChar(n, k) { let prev = "A"; let cur = ""; // If N is 1 then return A if (n == 1) { return 'A'; } // Iterate a loop and generate // the recursive String for (let j = 2; j <= n; j++) { // Update current String cur = prev + "B"; // Change A to B and B to A for (let i = 0; i < prev.length; i++) { if (prev[i] == 'A') { prev[prev[i]] = 'B'; } else { prev[prev[i]] = 'A'; } } // Reverse the previous String prev = reverse(prev); cur += prev; prev = cur; } // Return the kth character return cur[k]; } let N = 4; let K = 3; document.write(findKthChar(N, K)); // This code is contributed by mukesh07.</script> |
Output:
B
Time Complexity: O(N2)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
