Given two arrays of strings arr[] and k[] of size N and M respectively, the task is to sort the array arr[] after replacing each array element arr[i] with the GCD of arr[i] and k[j], where 0 ? i < N and 0 ? j < M. If it is not possible to sort the array, then print -1.
Note: The GCD of two strings A and B is the smallest string, which when concatenated multiple times, becomes equal to A and B. If no such string exists, return an empty string.
Examples:
Input: arr[] = { ‘neveropen’, ‘for’, ‘neveropen’ }, k[] = { ‘neveropenneveropen’, ‘for’ }
Output: { ‘ ‘, ‘for’, ‘neveropen’ }
Explanation:
arr[0] = GCD(‘neveropen’, ‘for’) = ‘ ‘
arr[1] = GCD(‘for’, ‘for’) = ‘for’
arr[2] = GCD(‘neveropen’, ‘neveropenneveropen’) = ‘neveropen’
arr[0] < arr[1] < arr[2]Input: arr[] = { ‘aacd’, ‘abdc’, ‘acac’, ‘aaaa’ }, k[] = {‘aa’, ‘ac’}
Output: -1
Approach: The given problem can be solved greedily. Follow the steps below to solve the problem:
- Initialize a variable say, prev = ” ( empty string), to store the previous string in the sorted order.
- Traverse the array, for i in range [0, N – 1]
- Calculate the GCD with each string of arr[i] with k[j], for j in range [0, M – 1].
- Find the minimum string say, optEle lexicographically greater than prev
- Update arr[i] = optEle
- Update prev = arr[i]
- If the array is sorted in ascending order. Print the array
- Otherwise, print -1.
Below is the implementation.
C++
#include <bits/stdc++.h>using namespace std;// Function to find GCD of two stringsstring StringGCD(string a, string b){ // # Length of gcd of two strings int gcd = __gcd(a.length(), b.length()); string s1 = "", s2 = ""; // creating two strings of length gcd from a and b respectively for (int i = 0; i < gcd; i++) { s1.push_back(a[i]); } for (int i = 0; i < gcd; i++) { s2.push_back(b[i]); } if (s1 == s2) { string temp1 = "", temp2 = ""; for (int i = 1; i <= (int)(b.length() / gcd); i++) { temp1 += a; } for (int i = 1; i <= (int)(a.length() / gcd); i++) { temp2 += b; } if (temp1 == temp2) return s1; } // # GCD of strings does not exist return " ";}// Function to check if the array is// sorted in increasing order or notbool isIncreasing(vector<string> arr) { for (int i = 0; i < arr.size() - 1; i++) { if (arr[i] >= arr[i + 1]) return false; } return true;}// Function to check if arr[] can// be sorted in increasing ordervector<string> sortByGcd(vector<string> arr, vector<string> k) { // Previous string string prev = ""; // Iterate through the array for (string &i : arr) { // Initialize optimal // element by arr[i] string optEle = i; // Flag to find first // string > prev bool flag = true; for (string j : k) { // Gcd of two strings string Ele = StringGCD(i, j); // If Ele > prev and flag is set if (Ele > prev && flag) { // Update optEle optEle = Ele; // Update Flag flag = false; } // If Ele > prev if (Ele > prev) { // Update optEle optEle = min(optEle, Ele); } } // Update arr[i] by optEle i = optEle; // Update prev by arr[i] prev = i; } // check is arr[] is sorted in ascending order vector<string> ans; if (isIncreasing(arr)) { return arr; } // Sorted order is not possible return ans;}// Driver Codeint main() { vector<string> arr = {"neveropen", "for", "neveropen"}; vector<string> k = {"neveropen", "for"}; for (string str : sortByGcd(arr, k)) { cout << str << " "; } return 0;}/* This code is contributed by Aditya Sharma */ |
Java
import java.util.*;class GFG { static int __gcd(int a, int b) { if (b == 0) { return a; } return __gcd(b, a % b); } // Function to find GCD of two strings static String StringGCD(String a, String b) { // Length of gcd of two strings int gcd = __gcd(a.length(), b.length()); String s1 = "", s2 = ""; // creating two strings of length gcd from a and b // respectively for (int i = 0; i < gcd; i++) { s1 += a.charAt(i); } for (int i = 0; i < gcd; i++) { s2 += b.charAt(i); } if (s1.equals(s2)) { String temp1 = "", temp2 = ""; for (int i = 1; i <= b.length() / gcd; i++) { temp1 += a; } for (int i = 1; i <= a.length() / gcd; i++) { temp2 += b; } if (temp1.equals(temp2)) return s1; } // GCD of strings does not exist return " "; } // Function to check if the array is // sorted in increasing order or not static boolean isIncreasing(List<String> arr) { for (int i = 0; i < arr.size() - 1; i++) { if (arr.get(i).compareTo(arr.get(i + 1)) >= 0) return false; } return true; } // Function to check if arr[] can // be sorted in increasing order static List<String> sortByGcd(List<String> arr, List<String> k) { // Previous string String prev = ""; // Iterate through the array for (int i = 0; i < arr.size(); i++) { // Initialize optimal // element by arr[i] String optEle = arr.get(i); // Flag to find first // string > prev boolean flag = true; for (String j : k) { // Gcd of two strings String Ele = StringGCD(arr.get(i), j); // If Ele > prev and flag is set if (Ele.compareTo(prev) > 0 && flag) { // Update optEle optEle = Ele; // Update Flag flag = false; } // If Ele > prev if (Ele.compareTo(prev) > 0) { // Update optEle optEle = (optEle.compareTo(Ele) < 0) ? optEle : Ele; } } // Update arr[i] by optEle arr.set(i, optEle); // Update prev by arr[i] prev = arr.get(i); } // check is arr[] is sorted in ascending order if (isIncreasing(arr)) { return arr; } // Sorted order is not possible return new ArrayList<>(); } // Driver Code public static void main(String[] args) { List<String> arr = Arrays.asList("neveropen", "for", "neveropen"); List<String> k = Arrays.asList("neveropen", "for"); for (String str : sortByGcd(arr, k)) { System.out.print(str + " "); } }}// This code is contributed by lokeshpotta20. |
Python3
# Python implementation of the# above approach# Function to find gcd of two numbersdef GCD(a, b): if(b == 0): return a else: return GCD(b, a % b)# Function to find GCD of two stringsdef StringGCD(a, b): # Length of gcd of two strings gcd = GCD(len(a), len(b)) if a[:gcd] == b[:gcd]: if a*(len(b)//gcd) == b*(len(a)//gcd): return a[:gcd] # GCD of strings does not exist return ' '# Function to check if the array is# sorted in increasing order or notdef isIncreasing(arr): for i in range(len(arr)-1): if arr[i] >= arr[i + 1]: return False return True# Function to check if arr[] can# be sorted in increasing orderdef sortByGcd(arr, k): # Previous string prev = '' # Iterate through the array for i in range(len(arr)): # Initialize optimal # element by arr[i] optEle = arr[i] # Flag to find first # string > prev flag = True for idx in range(len(k)): # Gcd of two strings Ele = StringGCD(arr[i], k[idx]) # If Ele > prev and flag is set if Ele > prev and flag: # Update optEle optEle = Ele # Update Flag flag = False # If Ele > prev if Ele > prev: # Update optEle optEle = min(optEle, Ele) # Update arr[i] by optEle arr[i] = optEle # Update prev by arr[i] prev = arr[i] # Check is arr[] is sorted in ascending order if isIncreasing(arr): return arr # Sorted order is not possible else: return -1# Driver Codearr = ['neveropen', 'for', 'neveropen']k = ['neveropen', 'for']print(sortByGcd(arr, k)) |
C#
using System;using System.Collections.Generic;class GFG { static int __gcd(int a, int b) { if (b == 0) { return a; } return __gcd(b, a % b); } // Function to find GCD of two strings static string StringGCD(string a, string b) { // Length of gcd of two strings int gcd = __gcd(a.Length, b.Length); string s1 = "", s2 = ""; // creating two strings of length gcd from a and b // respectively for (int i = 0; i < gcd; i++) { s1 += a[i]; } for (int i = 0; i < gcd; i++) { s2 += b[i]; } if (s1.Equals(s2)) { string temp1 = "", temp2 = ""; for (int i = 1; i <= b.Length / gcd; i++) { temp1 += a; } for (int i = 1; i <= a.Length / gcd; i++) { temp2 += b; } if (temp1.Equals(temp2)) return s1; } // GCD of strings does not exist return " "; } // Function to check if the array is // sorted in increasing order or not static bool isIncreasing(List<string> arr) { for (int i = 0; i < arr.Count - 1; i++) { if (string.Compare(arr[i], arr[i + 1]) >= 0) return false; } return true; } // Function to check if arr[] can // be sorted in increasing order static List<string> sortByGcd(List<string> arr, List<string> k) { // Previous string string prev = ""; // Iterate through the array for (int i = 0; i < arr.Count; i++) { // Initialize optimal // element by arr[i] string optEle = arr[i]; // Flag to find first // string > prev bool flag = true; foreach(string j in k) { // Gcd of two strings string Ele = StringGCD(arr[i], j); // If Ele > prev and flag is set if (Ele.CompareTo(prev) > 0 && flag) { // Update optEle optEle = Ele; // Update Flag flag = false; } // If Ele > prev if (Ele.CompareTo(prev) > 0) { // Update optEle optEle = (optEle.CompareTo(Ele) < 0) ? optEle : Ele; } } // Update arr[i] by optEle arr[i] = optEle; // Update prev by arr[i] prev = arr[i]; } // check is arr[] is sorted in ascending order if (isIncreasing(arr)) { return arr; } // Sorted order is not possible return new List<string>(); } // Driver Code public static void Main(string[] args) { List<string> arr = new List<string>{ "neveropen", "for", "neveropen" }; List<string> k = new List<string>{ "neveropen", "for" }; foreach(string str in sortByGcd(arr, k)) { Console.Write("'" + str + "', "); } }}// This code is contributed by phasing17. |
Javascript
<script>// Javascript implementation of the // above approach// Function to find gcd of two numbersfunction GCD(a, b) { if (b == 0) return a; else return GCD(b, a % b);}// Function to find GCD of two strings function StringGCD(a, b) { if (a + b !== b + a) { // not possible // no common element return ""; } else if (a == b) { return a; } else if (a.length > b.length) { return StringGCD(a.slice(str2.length), b); } else { return StringGCD(b.slice(str1.length), a); }}// Function to check if the array is // sorted in increasing order or //notfunction isIncreasing(arr) { for (let i = 0; i < (arr.length - 1); i++) { if (arr[i] >= arr[i + 1]) return false; } return true;}// Function to check if arr[] can// be sorted in increasing orderfunction sortByGcd(arr, k) { // Previous string var prev = ""; // Iterate through the array for (let i = 0; i < (arr.length); i++) { // Initialize optimal // element by arr[i] optEle = arr[i]; // Flag to find first // string > prev var flag = true; for (let idx = 0; idx < k.length; idx++) { // Gcd of two strings var Ele = StringGCD(arr[i], k[idx]); // If Ele > prev and flag is set if (Ele > prev && flag) { // Update optEle optEle = Ele; // Update Flag flag = false; } // If Ele > prev if (Ele > prev) { // Update optEle optEle = Math.min(optEle, Ele); } } // Update arr[i] by optEle if (isNaN(optEle)) { arr[i] = ' '; } else { arr[i] = optEle; } // Update prev by arr[i] prev = arr[i] // Check is arr[] is sorted in ascending order if (isIncreasing(arr)) { return arr; } // Sorted order is not possible else return -1; }}// Driver Codevar arr = ['neveropen', 'for', 'neveropen'];var k = ['neveropen', 'for'];console.log(sortByGcd(arr, k));// This code is contributed by akashish__</script> |
Output
[' ', 'for', 'neveropen']
Time Complexity: O(N * K * log(min(N, K))
Auxiliary Space: O(1)
