Given a string S consisting of N digits from [1, 9] and a positive integer K and X. Every day each character of the string is replaced by its frequency and value. The task is to find the Kth character of the string after X days.
Examples:
Input: S = “1214”, K = 10, X = 3
Output: 4
Explanation:
1st day = “12214444”
2nd day = “1222214444444444444444”
3rd day = “122222222444444444444444444444444444444444444444444444444”
So, 10th character after 3rd day is 4.Input: S =”123″, K = 6, X = 2
Output: 3
Naive Approach: The simplest approach to solve the problem is to create the string by appending the digits in the string digitX times and finding the Kth character of the string.
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the Kth character// after X dayschar FindKthChar(string str, long long K, int X){ string s = str; for (int i = 0; i < X; i++) { string res = ""; for (int j = 0; j < s.size(); j++) { int count = s[j] - '0'; while (count--) { res += s[j]; } } s = res; } return s[K - 1];}// Driver Codeint main(){ // Given Input string str = "1214"; long long K = 10; int X = 3; // Function Call char ans = FindKthChar(str, K, X); cout << ans << "\n"; return 0;} |
Java
import java.util.*;class Gfg { // Function to find the Kth character // after X days static char findKthChar(String str, long K, int X) { String s = str; for (int i = 0; i < X; i++) { String res = ""; for (int j = 0; j < s.length(); j++) { int count = s.charAt(j) - '0'; while (count-- > 0) { res += s.charAt(j); } } s = res; } return s.charAt((int)(K - 1)); } public static void main(String[] args) { // Given Input String str = "1214"; long K = 10; int X = 3; // Function Call char ans = findKthChar(str, K, X); System.out.println(ans); }} |
Python3
# Function to find the Kth character # after X days def FindKthChar(str, K, X): s = str for i in range(X): res = "" for j in range(len(s)): count = int(s[j]) res += s[j] * count s = res return s[K - 1]# Given Inputstr = "1214"K = 10X = 3# Function Callans = FindKthChar(str, K, X)print(ans)#This code is contributed by shivamsharma215 |
C#
using System;class Gfg{ // Function to find the Kth character // after X days static char findKthChar(string str, long K, int X) { string s = str; for (int i = 0; i < X; i++) { string res = ""; for (int j = 0; j < s.Length; j++) { int count = s[j] - '0'; while (count-- > 0) { res += s[j]; } } s = res; } return s[(int)(K - 1)]; } public static void Main(string[] args) { // Given Input string str = "1214"; long K = 10; int X = 3; // Function Call char ans = findKthChar(str, K, X); Console.WriteLine(ans); }}// This code is contributed by divya_p123. |
Javascript
// JavaScript program for the above approach// function to find the kth character// after x daysfunction FindKthChar(str, K, X){ let s = str; for(let i = 0; i<X; i++){ let res = ""; for(let j = 0; j<s.length; j++){ let count = s[j] - '0'; while(count--){ res += s[j]; } } s = res; } return s[K-1];}// driver codelet str = "1214";let K = 10;let X = 3;// function calllet ans = FindKthChar(str, K, X);console.log(ans);// THIS CODE IS CONTRIBUTED BY YASH AGARWAL(YASHAGARWAL2852002) |
Output
1
Time Complexity: O(?digit[i]X) for i in range [0, N-1]
Auxiliary Space: O(?digit[i]X) for i in range [0, N-1]
Efficient Approach: The above approach can be optimized further by instead of creating a string add digitX to the sum and check if sum > K. Follow the steps below to solve the problem:
- Initialize a variable, say sum that stores the sum of the character of the string after X days.
- Initialize a variable, say ans that stores the Kth characters after X days.
- Iterate in the range [0, N-1] and perform the following steps:
- Initialize a variable say range as (S[i] – ‘0’)X and add it to the variable sum.
- If sum>=K, return S, modify ans as S[i], and terminate the loop.
- Print the value of ans as the answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the Kth character// after X dayschar FindKthChar(string str, long long K, int X){ // Variable to store the KthChar char ans; int sum = 0; // Traverse the string for (int i = 0; i < str.length(); i++) { // Convert char into int int digit = str[i] - '0'; // Calculate characters int range = pow(digit, X); sum += range; // If K is less than sum // than ans = str[i] if (K <= sum) { ans = str[i]; break; } } // Return answer return ans;}// Driver Codeint main(){ // Given Input string str = "123"; long long K = 9; int X = 3; // Function Call char ans = FindKthChar(str, K, X); cout << ans << "\n"; return 0;} |
Java
// Java program for the above approachclass GFG{// Function to find the Kth character// after X daysstatic char FindKthChar(String str, int K, int X){ // Variable to store the KthChar char ans = ' '; int sum = 0; // Traverse the string for(int i = 0; i < str.length(); i++) { // Convert char into int int digit = (int)str.charAt(i) - 48; // Calculate characters int range = (int)Math.pow(digit, X); sum += range; // If K is less than sum // than ans = str[i] if (K <= sum) { ans = str.charAt(i); break; } } // Return answer return ans;}// Driver codepublic static void main(String[] args){ // Given Input String str = "123"; int K = 9; int X = 3; // Function Call char ans = FindKthChar(str, K, X); System.out.println(ans);}}// This code is contributed by abhinavjain194 |
Python3
# Python3 program for the above approachimport math# Function to find the Kth character# after X daysdef FindKthChar(Str, K, X): # Variable to store the KthChar ans = ' ' Sum = 0 # Traverse the string for i in range(len(Str)): # Convert char into int digit = ord(Str[i]) - 48 # Calculate characters Range = int(math.pow(digit, X)) Sum += Range # If K is less than sum # than ans = str[i] if (K <= Sum): ans = Str[i] break # Return answer return ans# Given InputStr = "123"K = 9X = 3# Function Callans = FindKthChar(Str, K, X)print(ans)# This code is contributed by divyeshrabadiya07. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function to find the Kth character// after X daysstatic char FindKthChar(string str, int K, int X){ // Variable to store the KthChar char ans = ' '; int sum = 0; // Traverse the string for(int i = 0; i < str.Length; i++) { // Convert char into int int digit = (int)str[i] - 48; // Calculate characters int range = (int)Math.Pow(digit, X); sum += range; // If K is less than sum // than ans = str[i] if (K <= sum) { ans = str[i]; break; } } // Return answer return ans;}// Driver Codepublic static void Main(){ // Given Input string str = "123"; int K = 9; int X = 3; // Function Call char ans = FindKthChar(str, K, X); Console.Write(ans);}}// This code is contributed by SURENDRA_GANGWAR |
Javascript
<script>// javascript program for the above approach // Function to find the Kth character // after X days function FindKthChar( str , K , X) { // Variable to store the KthChar var ans = ""; var sum = 0; // Traverse the string for (i = 0; i < str.length; i++) { // Convert char into int var digit = parseInt( str[i]); // Calculate characters var range = parseInt( Math.pow(digit, X)); sum += range; // If K is less than sum // than ans = str[i] if (K <= sum) { ans = str[i]; break; } } // Return answer return ans; } // Driver code // Given Input var str = "123"; var K = 9; var X = 3; // Function Call var ans = FindKthChar(str, K, X); document.write(ans);// This code contributed by gauravrajput1 </script> |
Output
2
Time Complexity: O(N), since there is only one loop to carry out the operations the overall complexity turns out to be O(N)
Auxiliary Space: O(1), since there is no extra array or data structure used, it takes constant space.
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!
