Given a binary string S of size N, the task is to find the maximum possible value in exactly K step, where in each step, perform XOR of two substrings of S (possibly intersecting, possibly the same, possibly non-intersecting).
Examples:
Input: string S =”1010010″, K = 2
Output: “1111110”
Explanation:
In the first step, choose one substring as 1010010 and another as 101001, the XOR of these both strings will be 1111011.
In the second step, Choose one substring as 1111011 and another as 101, the XOR of these both strings will be 1111110, which is the maximum possible value you can get in K steps.Input: string S =”11010″, K = 1
Output: “11111”
Explanation: Choose one substring as 11010 and another substring as 101, the XOR of these both strings will be 11111, which is the maximum possible value you can get in one step.
Approach: The given problem can be solved by using the below idea.
Choose one substring as String S because it has maximum possible decimal value and other as the size – index of leftmost 0 because we have to maximise the size of substring and convert 0 to 1 and do this step K times.
Follow the steps to solve this problem:
- Count the number of 1s and 0s in the string.
- If the count of 1s is equal to the length of the string, then there can be two cases
- If K is a multiple of 2, i.e., even we can pick a substring ‘1’ and XOR it even times, so the string will remain unchanged.
- Otherwise, we will pick a substring ‘1’ and XOR it, so only the least significant bit will be changed to ‘0’.
- If the count of 0s is equal to the length of the string, return 0 as no 1 is there.
- Take one substring as S and another (say t) is any possible substring of size size N-idx where idx is the index of the leftmost 0.
- Take XOR of S and t, this is the maximum possible value.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach#include <bits/stdc++.h>#define ll long longusing namespace std;// Function to insert n 0s in the// beginning of the given stringvoid addZeros(string& str, int n){ for (int i = 0; i < n; i++) { str = "0" + str; }}// Function to return the XOR// of the given stringsstring getXOR(string a, string b){ // Lengths of the given strings int aLen = a.length(); int bLen = b.length(); // Make both the strings of equal lengths // by inserting 0s in the beginning if (aLen > bLen) { addZeros(b, aLen - bLen); } else if (bLen > aLen) { addZeros(a, bLen - aLen); } // Updated length int len = max(aLen, bLen); // To store the resultant XOR string res = ""; for (int i = 0; i < len; i++) { if (a[i] == b[i]) res += "0"; else res += "1"; } return res;}// Function to find max Xor of one stringstring maxValue(string S){ // Initialize variables ll n = S.size(); // Flag to get index of leftmost // zero bool f = 1; ll Idx, Count0 = 0, Count1 = 0; // Count the number of 1's and 0's in // the string and also index of left // most 0 in the string for (ll i = 0; i < n; i++) { // Character is equal to 1 if (S[i] == '1') { Count1++; } // Character is equal to 0 else { if (f) { // Storing the index of // leftmost zero Idx = i; f = 0; } Count0++; } } // If all are 1's in the string if (Count1 == n) { return getXOR(S, "1"); } // If all are 0's in the string // print 0 if (Count0 == n) { return "0"; } // Find another substring string t = S.substr(Idx, n - Idx); // Find it's size ll size = t.size(); string dec = t; string Max = ""; // First and second substring string t1 = "", t2 = ""; // Find second substring for (ll j = 0; j < n; j++) { if (j < size) { t1 += S[j]; } else { string dec1 = t1; // Function to calculate XOR of // two string string res = getXOR(dec, dec1); if (res > Max) { Max = res; t2 = t1; } t1 = t1.substr(1); t1 += S[j]; } } string dec1 = t1; string res = getXOR(dec1, dec); if (res > Max) { Max = res; t2 = t; } // First and second string string d1 = S; string d2 = t2; // Xor of first and second substring string ans = getXOR(d1, d2); Idx = -1; // Remove leading zeroes for (ll i = 0; i < ans.size(); i++) { if (ans[i] != '0') { Idx = i; break; } } if (Idx == -1) { return "0"; } // Return resultant substring return ans.substr(Idx);}// Function to calculate maximum XOR value// in exactly K stepsstring solve(string s, int K){ int i = 0; while (i < K) { // Function call to find maximum // XOR value of s s = maxValue(s); i++; } return s;}// Driver Codeint main(){ string s = "1010010"; int K = 2; // Function call cout << solve(s, K) << endl; return 0;} |
Java
// Java code to implement the approachimport java.io.*;class GFG { // Function to return the XOR // of the given strings static String getXOR(String a, String b) { // Lengths of the given strings int aLen = a.length(); int bLen = b.length(); // Make both the strings of equal lengths // by inserting 0s in the beginning if (aLen > bLen) { b = addZeros(b, aLen - bLen); } else if (bLen > aLen) { a = addZeros(a, bLen - aLen); } // Updated length int len = Math.max(aLen, bLen); // To store the resultant XOR String res = ""; for (int i = 0; i < len; i++) { if (a.charAt(i) == b.charAt(i)) res += "0"; else res += "1"; } return res; } // Function to insert n 0s in the // beginning of the given string static String addZeros(String s, int numZeros) { for (int i = 0; i < numZeros; i++) { s = "0" + s; } return s; } // Function to find max Xor of one string static String maxValue(String S) { // Initialize variables int n = S.length(); // Flag to get index of leftmost // zero boolean f = true; int Idx = 0, Count0 = 0, Count1 = 0; // Count the number of 1's and 0's in // the string and also index of left // most 0 in the string for (int i = 0; i < n; i++) { // Character is equal to 1 if (S.charAt(i) == '1') { Count1++; } // Character is equal to 0 else { if (f) { // Storing the index of // leftmost zero Idx = i; f = false; } Count0++; } } // If all are 1's in the string if (Count1 == n) { return getXOR(S, "1"); } // If all are 0's in the string // print 0 if (Count0 == n) { return "0"; } // Find another substring String t = S.substring(Idx, n); // Find it's size int size = t.length(); String dec = t; String Max = ""; // First and second substring String t1 = "", t2 = ""; // Find second substring for (int j = 0; j < n; j++) { if (j < size) { t1 += S.charAt(j); } else { String dec1 = t1; // Function to calculate XOR of // two string String res = getXOR(dec, dec1); if (res.compareTo(Max) > 0) { Max = res; t2 = t1; } t1 = t1.substring(1); t1 += S.charAt(j); } } String dec1 = t1; String res = getXOR(dec1, dec); if (res.compareTo(Max) > 0) { Max = res; t2 = t; } // First and second string String d1 = S; String d2 = t2; // Xor of first and second substring String ans = getXOR(d1, d2); Idx = -1; // Remove leading zeroes for (int i = 0; i < ans.length(); i++) { if (ans.charAt(i) != '0') { Idx = i; break; } } if (Idx == -1) { return "0"; } // Return resultant substring return ans.substring(Idx); } // Function to calculate maximum XOR value // in exactly K steps static String solve(String s, int K) { int i = 0; while (i < K) { // Function call to find maximum XOR value of s s = maxValue(s); i++; } return s; } public static void main(String[] args) { String s = "1010010"; int K = 2; // Function call System.out.println(solve(s, K)); }}// This code is contributed by lokesh. |
Python3
# python codedef add_zeros(s: str, n: int) -> str: return "0" * n + sdef get_xor(a: str, b: str) -> str: a_len = len(a) b_len = len(b) if a_len > b_len: b = add_zeros(b, a_len - b_len) elif b_len > a_len: a = add_zeros(a, b_len - a_len) len_ = max(a_len, b_len) res = "" for i in range(len_): if a[i] == b[i]: res += "0" else: res += "1" return resdef maxValue(S: str) -> str: n = len(S) f = True Idx = 0 Count0 = 0 Count1 = 0 for i in range(n): if S[i] == "1": Count1 += 1 else: if f: Idx = i f = False Count0 += 1 if Count1 == n: return get_xor(S, "1") if Count0 == n: return "0" t = S[Idx:] size = len(t) dec = t Max = "" t1 = "" t2 = "" for j in range(n): if j < size: t1 += S[j] else: dec1 = t1 res = get_xor(dec, dec1) if res > Max: Max = res t2 = t1 t1 = t1[1:] t1 += S[j] dec1 = t1 res = get_xor(dec1, dec) if res > Max: Max = res t2 = t d1 = S d2 = t2 ans = get_xor(d1, d2) Idx = -1 for i in range(len(ans)): if ans[i] != "0": Idx = i break if Idx == -1: return "0" return ans[Idx:]def solve(s, K): i = 0 while (i < K): s = maxValue(s) i += 1 return ss = "1010010"K = 2print(solve(s, K))# This code is contributed by ksam24000 |
C#
// C# code to implement the approachusing System;public class GFG { // Function to return the XOR // of the given strings static string getXOR(string a, string b) { // Lengths of the given strings int aLen = a.Length; int bLen = b.Length; // Make both the strings of equal lengths // by inserting 0s in the beginning if (aLen > bLen) { b = AddZeros(b, aLen - bLen); } else if (bLen > aLen) { a = AddZeros(a, bLen - aLen); } // Updated length int len = Math.Max(aLen, bLen); // To store the resultant XOR string res = ""; for (int i = 0; i < len; i++) { if (a[i] == b[i]) res += "0"; else res += "1"; } return res; } // Function to insert n 0s in the // beginning of the given string static string AddZeros(string s, int numZeros) { for (int i = 0; i < numZeros; i++) { s = "0" + s; } return s; } // Function to find max Xor of one string static string maxValue(string S) { // Initialize variables int n = S.Length; // Flag to get index of leftmost // zero bool f = true; int Idx = 0, Count0 = 0, Count1 = 0; // Count the number of 1's and 0's in // the string and also index of left // most 0 in the string for (int i = 0; i < n; i++) { // Character is equal to 1 if (S[i] == '1') { Count1++; } // Character is equal to 0 else { if (f) { // Storing the index of // leftmost zero Idx = i; f = false; } Count0++; } } // If all are 1's in the string if (Count1 == n) { return getXOR(S, "1"); } // If all are 0's in the string // print 0 if (Count0 == n) { return "0"; } // Find another substring string t = S.Substring((int)Idx, (int)(n - Idx)); // Find it's size int size = t.Length; string dec = t; string Max = ""; // First and second substring string t1 = "", t2 = ""; // Find second substring for (int j = 0; j < n; j++) { if (j < size) { t1 += S[j]; } else { string dec1 = t1; // Function to calculate XOR of // two string string res = getXOR(dec, dec1); if (res.CompareTo(Max) > 0) { Max = res; t2 = t1; } t1 = t1.Substring(1); t1 += S[j]; } } string temp1 = t1; string temp2 = getXOR(temp1, dec); if (temp2.CompareTo(Max) > 0) { Max = temp2; t2 = t; } // First and second string string d1 = S; string d2 = t2; // Xor of first and second substring string ans = getXOR(d1, d2); Idx = -1; // Remove leading zeroes for (int i = 0; i < ans.Length; i++) { if (ans[i] != '0') { Idx = i; break; } } if (Idx == -1) { return "0"; } // Return resultant substring return ans.Substring(Idx); } // Function to calculate maximum XOR value // in exactly K steps static string solve(string s, int K) { int i = 0; while (i < K) { // Function call to find maximum XOR value of s s = maxValue(s); i++; } return s; } static public void Main() { // Code string s = "1010010"; int K = 2; // Function call Console.WriteLine(solve(s, K)); }}// This code is contributed by lokeshmvs21. |
Javascript
// JavaScript code to implement the approach// Function to insert n 0s in the// beginning of the given stringconst addZeros = (str, n) => { for (let i = 0; i < n; i++) { str = "0" + str; } return str;}// Function to return the XOR// of the given stringsconst getXOR = (a, b) => { // Lengths of the given strings let aLen = a.length; let bLen = b.length; // Make both the strings of equal lengths // by inserting 0s in the beginning if (aLen > bLen) { b = addZeros(b, aLen - bLen); } else if (bLen > aLen) { a = addZeros(a, bLen - aLen); } // Updated length let len = Math.max(aLen, bLen); // To store the resultant XOR let res = ""; for (let i = 0; i < len; i++) { if (a[i] == b[i]) res += "0"; else res += "1"; } return res;}// Function to find max Xor of one stringconst maxValue = (S) => { // Initialize variables let n = S.length; // Flag to get index of leftmost // zero let f = 1; let Idx, Count0 = 0, Count1 = 0; // Count the number of 1's and 0's in // the string and also index of left // most 0 in the string for (let i = 0; i < n; i++) { // Character is equal to 1 if (S[i] == '1') { Count1++; } // Character is equal to 0 else { if (f) { // Storing the index of // leftmost zero Idx = i; f = 0; } Count0++; } } // If all are 1's in the string if (Count1 == n) { return getXOR(S, "1"); } // If all are 0's in the string // print 0 if (Count0 == n) { return "0"; } // Find another substring let t = S.substring(Idx, n); // Find it's size let size = t.length; let dec = t; let Max = ""; // First and second substring let t1 = "", t2 = ""; // Find second substring for (let j = 0; j < n; j++) { if (j < size) { t1 += S[j]; } else { let dec1 = t1; // Function to calculate XOR of // two string let res = getXOR(dec, dec1); if (res > Max) { Max = res; t2 = t1; } t1 = t1.substring(1); t1 += S[j]; } } let dec1 = t1; let res = getXOR(dec1, dec); if (res > Max) { Max = res; t2 = t; } // First and second string let d1 = S; let d2 = t2; // Xor of first and second substring let ans = getXOR(d1, d2); Idx = -1; // Remove leading zeroes for (let i = 0; i < ans.length; i++) { if (ans[i] != '0') { Idx = i; break; } } if (Idx == -1) { return "0"; } // Return resultant substring return ans.substring(Idx);}// Function to calculate maximum XOR value// in exactly K stepsconst solve = (s, K) => { let i = 0; while (i < K) { // Function call to find maximum // XOR value of s s = maxValue(s); i++; } return s;}// Driver Codelet s = "1010010";let K = 2;// Function callconsole.log(solve(s, K));// This code is contributed by rakeshsahni |
Output
1111110
Time Complexity: O(N2 * K)
Auxiliary Space: O(N)
Related Articles:
- Introduction to Strings – Data Structures and Algorithms Tutorials
- Introduction to Bitwise Algorithms – Data Structures and Algorithms Tutorials
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!
Share your thoughts in the comments
