Insert a Character in a Rotated String
Given an array of characters arr[] of size N and an integer K. You have to insert the characters into an empty string one by one such that every insertion is done after K positions to the right from the previous insertion and the string is circular. The task is to find the character after which the last insertion is done
Examples:
Input: arr[] = {β1β, β2β, β3β, β4β, β5β}, K = 2
Output: 1
After the first insertion string becomes β1β
After the second insertion string becomes β12β
After third insertion, as the previous insertion was at position 2.
So, the current insertion has to be at 2 + 2 i.e. 4th position.
Since, the string is circular so moving 2 positions to the right will
be β1|2β -> β12|β and the final string will be β123β
After the fourth insertion, β123β -> β1|23β -> β12|3β i.e. β1243β
After the fifth insertion, β1243β -> β1243|β -> β1|243β i.e. β15243β
The last character inserted after the character β1βInput: arr[] = {β1β, β2β, β3β, β4β, β5β}, K = 1
Output: 1
Final string is β15324β
Approach: For every character, insert it in the required position and also keep track of the previous position and the character after which the previous insertion was done. When all the characters have been inserted, print the character after which the last insertion was done.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to insert the character char Insert( char arr[], int n, int k) { // To store last position where // the insertion is done int ind = 0; // To store size of the string int sz = 0; // To store the modified string string s = "" ; // To store characters char ch = arr[0]; // Add first character to the string s += ch; // Update the size sz = 1; // Update the index of last insertion ind = 0; // Insert all other characters to the string for ( int i = 1; i < n; i++) { // Take the character ch = arr[i]; // Take substring upto ind string s1 = s.substr(0, ind + 1); // Take modulo value of k with // the size of the string int temp = k % sz; // Check if we need to move to // the start of the string int ro = temp - min(temp, sz - ind - 1); // If we don't need to move to start of the string if (ro == 0) { // Take substring from upto temp string s2 = s.substr(ind + 1, temp); // Take substring which will be after // the inserted character string s3 = s.substr(ind + temp + 1, sz - ind - temp - 1); // Insert into the string s = s1 + s2 + ch + s3; // Store new inserted position ind = s1.size() + s2.size(); // Store size of the new string // Technically sz + 1 sz = s.size(); } // If we need to move to start of the string else { // Take substring which will before // the inserted character string s2 = s.substr(0, ro); // Take substring which will be after // the inserted character string s3 = s.substr(ro, sz - ro); // Insert into the string s = s2 + ch + s3; // Store new inserted position ind = s2.size(); // Store size of the new string // Technically sz + 1 sz = s.size(); } } // Return the required character if (ind == 0) return s[sz - 1]; else return s[ind - 1]; } // Driver code int main() { char arr[] = { '1' , '2' , '3' , '4' , '5' }; int k = 2; int n = sizeof (arr) / sizeof (arr[0]); // Function call cout << Insert(arr, n, k); return 0; } |
Java
// Java implementation of the approach import java.util.*; class GFG{ // Function to insert the character public static char Insert( char arr[], int n, int k) { // To store last position where // the insertion is done int ind = 0 ; // To store size of the string int sz = 0 ; // To store the modified string String s = "" ; // To store characters char ch = arr[ 0 ]; // Add first character to the string s += ch; // Update the size sz = 1 ; // Update the index of last insertion ind = 0 ; // Insert all other characters to the string for ( int i = 1 ; i < n; i++) { // Take the character ch = arr[i]; // Take substring upto ind String s1 = s.substring( 0 , ind + 1 ); // Take modulo value of k with // the size of the string int temp = k % sz; // Check if we need to move to // the start of the string int ro = temp - Math.min(temp, sz - ind - 1 ); // If we don't need to move to // start of the string if (ro == 0 ) { // Take substring from upto temp String s2 = s.substring(ind + 1 , ind + 1 + temp); // Take substring which will be after // the inserted character String s3 = s.substring(ind + temp + 1 , sz); // Insert into the string s = s1 + s2 + ch + s3; // Store new inserted position ind = s1.length() + s2.length(); // Store size of the new string // Technically sz + 1 sz = s.length(); } // If we need to move to start of the string else { // Take substring which will before // the inserted character String s2 = s.substring( 0 , ro); // Take substring which will be after // the inserted character String s3 = s.substring(ro, sz); // Insert into the string s = s2 + ch + s3; // Store new inserted position ind = s2.length(); // Store size of the new string // Technically sz + 1 sz = s.length(); } } // Return the required character if (ind == 0 ) { return s.charAt(sz - 1 ); } else { return s.charAt(ind - 1 ); } } // Driver code public static void main(String []args) { char arr[] = { '1' , '2' , '3' , '4' , '5' }; int k = 2 ; int n = arr.length; // Function call System.out.println(Insert(arr, n, k)); } } // This code is contributed by avanitrachhadiya2155 |
Python3
# Python3 implementation of the approach # Function to insert the character def insert(arr: list , n: int , k: int ) - > chr : # To store last position where # the insertion is done ind = 0 # To store size of the string sz = 0 # To store the modified string s = "" # To store characters ch = arr[ 0 ] # Add first character to the string s + = ch # Update the size sz = 1 # Update the index of last insertion ind = 0 # Insert all other characters to the string for i in range ( 1 , n): # Take the character ch = arr[i] # Take substring upto ind s1 = s[ 0 :ind + 1 ] # Take modulo value of k with # the size of the string temp = k % sz # Check if we need to move to # the start of the string ro = temp - min (temp, sz - ind - 1 ) # If we don't need to move to start of the string if ro = = 0 : # Take substring from upto temp s2 = s[ind + 1 :ind + 1 + temp] # Take substring which will be after # the inserted character s3 = s[ind + temp + 1 :sz] # Insert into the string s = s1 + s2 + ch + s3 # Store new inserted position ind = len (s1) + len (s2) # Store size of the new string # Technically sz + 1 sz = len (s) # If we need to move to start of the string else : # Take substring which will before # the inserted character s2 = s[:ro] # Take substring which will be after # the inserted character s3 = s[ro:sz] # Insert into the string s = s2 + ch + s3 # Store new inserted position ind = len (s2) # Store size of the new string # Technically sz + 1 sz = len (s) # Return the required character if ind = = 0 : return s[sz - 1 ] else : return s[ind - 1 ] # Driver Code if __name__ = = "__main__" : arr = [ '1' , '2' , '3' , '4' , '5' ] k = 2 n = len (arr) # Function call print (insert(arr, n, k)) # This code is contributed by # sanjeev2552 |
C#
// C# implementation of the approach using System; class GFG{ // Function to insert the character static char Insert( char [] arr, int n, int k) { // To store last position where // the insertion is done int ind = 0; // To store size of the string int sz = 0; // To store the modified string String s = "" ; // To store characters char ch = arr[0]; // Add first character to the string s += ch; // Update the size sz = 1; // Update the index of last insertion ind = 0; // Insert all other characters to the string for ( int i = 1; i < n; i++) { // Take the character ch = arr[i]; // Take substring upto ind string s1 = s.Substring(0, ind + 1); // Take modulo value of k with // the size of the string int temp = k % sz; // Check if we need to move to // the start of the string int ro = temp - Math.Min(temp, sz - ind - 1); // If we don't need to move to // start of the string if (ro == 0) { // Take substring from upto temp string s2 = s.Substring(ind + 1, temp); // Take substring which will be after // the inserted character string s3 = s.Substring(ind + temp + 1, sz - ind - temp - 1); // Insert into the string s = s1 + s2 + ch + s3; // Store new inserted position ind = s1.Length + s2.Length; // Store size of the new string // Technically sz + 1 sz = s.Length; } // If we need to move to start of the string else { // Take substring which will before // the inserted character string s2 = s.Substring(0, ro); // Take substring which will be after // the inserted character string s3 = s.Substring(ro, sz - ro); // Insert into the string s = s2 + ch + s3; // Store new inserted position ind = s2.Length; // Store size of the new string // Technically sz + 1 sz = s.Length; } } // Return the required character if (ind == 0) { return s[sz - 1]; } else { return s[ind - 1]; } } // Driver code static public void Main() { char [] arr = { '1' , '2' , '3' , '4' , '5' }; int k = 2; int n = arr.Length; // Function call Console.WriteLine(Insert(arr, n, k)); } } // This code is contributed by rag2127 |
Javascript
<script> // Javascript implementation of the approach // Function to insert the character function Insert(arr,n,k) { // To store last position where // the insertion is done let ind = 0; // To store size of the string let sz = 0; // To store the modified string let s = "" ; // To store characters let ch = arr[0]; // Add first character to the string s += ch; // Update the size sz = 1; // Update the index of last insertion ind = 0; // Insert all other characters to the string for (let i = 1; i < n; i++) { // Take the character ch = arr[i]; // Take substring upto ind let s1 = s.substring(0, ind + 1); // Take modulo value of k with // the size of the string let temp = k % sz; // Check if we need to move to // the start of the string let ro = temp - Math.min(temp, sz - ind - 1); // If we don't need to move to // start of the string if (ro == 0) { // Take substring from upto temp let s2 = s.substring(ind + 1, ind + 1 + temp); // Take substring which will be after // the inserted character let s3 = s.substring(ind + temp + 1, sz); // Insert into the string s = s1 + s2 + ch + s3; // Store new inserted position ind = s1.length + s2.length; // Store size of the new string // Technically sz + 1 sz = s.length; } // If we need to move to start of the string else { // Take substring which will before // the inserted character let s2 = s.substring(0, ro); // Take substring which will be after // the inserted character let s3 = s.substring(ro, sz); // Insert into the string s = s2 + ch + s3; // Store new inserted position ind = s2.length; // Store size of the new string // Technically sz + 1 sz = s.length; } } // Return the required character if (ind == 0) { return s[sz - 1]; } else { return s[ind - 1]; } } // Driver code let arr=['1 ', ' 2 ', ' 3 ', ' 4 ', ' 5' ]; let k = 2; let n = arr.length; document.write(Insert(arr, n, k)); // This code is contributed by ab2127 </script> |
1
Time Complexity: O(n2), where n is the length of the given string.
Auxiliary Space: O(n)
Contact Us