Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Binary String MEX CodeChef Solution
Problem -Binary String MEX CodeChef Solution
This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.
Binary String MEX CodeChef Solution in C++17
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define EB emplace_back
#define MP make_pair
#define alli(o) (o).begin(), (o).end()
#define mset(m,v) memset(m,v,sizeof(m))
#define fr(i,n) for(llii i=0;i<(n);++i)
#define rep(i,a,b) for(lli i=a;i<=b;++i)
#define per(i,a,b) for(lli i=a;i>=b;i--)
#define remin(a,b) (a=min((a),(b)))
#define remax(a,b) (a=max((a),(b)))
#define sz(x) (lli)(x).size()
#define endl '\n'
typedef long long lli; typedef long double ld;
typedef pair<lli, lli> ii; typedef vector<lli> vi;
typedef vector<ii> vii; typedef vector<vi> graph;
long long MOD = 1000000007; long double EPS = 1e-9;
#define inf 1000000000000000005
//-----
lli inv(lli i) {if (i == 1) return 1; return (MOD - ((MOD / i) * inv(MOD % i)) % MOD) % MOD;}
lli MOD_mul(lli a, lli b) {a = a % MOD; b = b % MOD; return (((a * b) % MOD) + MOD) % MOD;}
lli MOD_add(lli a, lli b) {a = a % MOD; b = b % MOD; return (((a + b) % MOD) + MOD) % MOD;}
lli gcd(lli a, lli b) { if (b == 0) return a; return gcd(b, a % b);}
lli ceil_div(lli a, lli b) {return a % b == 0 ? a / b : a / b + 1;}
lli pwr(lli a, lli b) {a %= MOD; lli res = 1; while (b > 0) {if (b & 1) res = res * a % MOD; a = a * a % MOD; b >>= 1;} return res;}
//----------------
vector<int> d = { -1, 0, 1, 0, -1};
vector<char> di = {'U', 'R', 'D', 'L'};
vector<vector<lli>> g;
vector<vector<lli>> f;
vector<lli> vis;
vector<int> par;
vector<lli> v;
lli n, m, k;
lli x;
bool ok;
set<lli> all;
vector<lli> pre;
vi primes;
vector<set<lli>> bg;
lli ans = 1;
// void dfs(int node, lli c, lli cnt) {
// vis[node] = 1LL;
// ans *= cnt;
// ans %= MOD;
// lli x = max(cnt - 1LL, c - 2LL);
// for (auto v : g[node]) {
// if (!vis[v]) {
// dfs(v, c, x);
// x--;
// }
// }
// }
// lli bfs(lli c){
// queue<ii> q;
// q.push({1LL, 0});
// int d = 0;
// lli ans = 1;
// lli prev = 0;
// while(!q.empty()){
// int size = q.size();
// for(int i = 0 ; i < size; i++){
// if(d )
// }
// }
// }
void solve() {
string s;
cin >> s;
n = s.size();
vi next0(n, inf), next1(n, inf), dp(n, 0);
lli n0 = inf, n1 = inf;
lli cnt = 0;
bool zero = false, one = false;
for (int i = n - 1; i >= 0; i--) {
next0[i] = n0;
next1[i] = n1;
dp[i] = cnt;
if (s[i] == '1') {
one = true;
n1 = i;
}
if (s[i] == '0') {
n0 = i;
zero = true;
}
if (one && zero) {
cnt++;
one = zero = false;
}
}
if (n0 == inf) {
cout << "0" << endl;
return;
} else if (n1 == inf) {
cout << "1" << endl;
return;
}
lli next = n1;
string res = "";
while (1) {
res += s[next];
n0 = next0[next];
n1 = next1[next];
if (n0 == inf) {
res += '0';
break;
} else if (n1 == inf) {
res += '1';
break;
}
if (dp[n0] <= dp[n1]) {
next = n0;
} else {
next = n1;
}
}
cout << res << endl;
}
int main() {
// #ifndef ONLINE_JUDGE
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// #endif
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cout << fixed;
cout << setprecision(15);
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
Binary String MEX CodeChef Solution in C++14
#include <iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<unordered_map>
#include<climits>
using namespace std;
unordered_map<int,pair<int,char> > mapping;
unordered_map<int,int> jmp_index;
string s;
int getLowest(int index){
if(mapping.count(index)){
return mapping[index].first;
}
// to take a zero
pair<int,int> p={INT_MAX,'-'};
int index0=index+1;
{
for(index0;index0<s.size();index0++){
if(s[index0]=='0'){
break;
}
}
if(index0==s.size()){
jmp_index[index]=index0;
p={1,'0'};
}
else{
int value=getLowest(index0);
p={value+1,'0'};
jmp_index[index]=index0;
}
}
int index1=index+1;
{
for(index1;index1<s.size();index1++){
if(s[index1]=='1'){
break;
}
}
if(index1==s.size()){
if(p.first!=1){
p={1,'1'};
jmp_index[index]=index1;
}
}
else{
int value=getLowest(index1);
if(value+1<p.first){
p={value+1,'1'};
jmp_index[index]=index1;
}
}
}
mapping[index]=p;
return p.first;
}
int main() {
int test;
cin>>test;
while(test--){
cin>>s;
int index=0;
for(index=0;index<s.size()&&s[index]!='0';index++){}
if(index==s.size()){
cout<<"0"<<endl;
continue;
}
for(index=0;index<s.size()&&s[index]!='1';index++){}
if(index==s.size()){
cout<<"1"<<endl;
continue;
}
else{
int value=getLowest(index);
string ans="1";
pair<int,int> p=mapping[index];
while(value--){
ans+=string(1,p.second);
index=jmp_index[index];
p=mapping[index];
}
cout<<ans<<endl;
mapping.clear();
jmp_index.clear();
}
}
return 0;
}Binary String MEX CodeChef Solution in PYTH 3
# cook your dish here
# cook your dish here
t=int(input())
for i in range(0,t):
s=input()
l=len(s)
next0=[-1 for x in range(0,l)]
next1=[-1 for x in range(0,l)]
lens =[0 for x in range (0,l)]
j=l-1
z=o=0
c=1
n0=-1
n1=-1
while(j>=0):
lens[j]=c
next0[j]=n0
next1[j]=n1
if(s[j]=='0'):
z=1
n0=j
else:
o=1
n1=j
if(z==1&o==1):
c=c+1
z=o=0
j=j-1
if(n0==-1):
print("0")
continue
if(n1==-1):
print("1")
continue
str=""
j=n1
while(True):
str=str+s[j]
if(next0[j]==-1):
str=str+"0"
break
elif(next1[j]==-1):
str=str+"1"
break
elif(lens[next0[j]]<=lens[next1[j]]):
j=next0[j]
else:
j=next1[j]
print(str)Binary String MEX CodeChef Solution in C
#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char st[1000007];
int main()
{
long a,b,c,d,e,f,g,i,j,k,l,m,n,o,p,q,r,s,t;
char st2[2][1000007];
scanf("%ld", &t);
while(t--)
{
scanf("%s", st);
i=0;
k=0;
j=0;
while((st[i] != '1') && (st[i] != '\0'))
{
i++;
}
st2[0][j] = st[i];
j++;
//printf("hello");
while(st[i] != '\0')
{
if(st[i] == '1')
{
if(st[i+1] == '1')
{
while((st[i] != '0') && (st[i] != '\0'))
{
i++;
}
if(k == 2)
{
st2[0][j-1] = '0';
}
st2[1][j] = '0';
k = 0;
st2[0][j] = st[i];
j++;
}
else if(st[i+1] == '0')
{
k = 0;
i++;
k++;
while((st[i] != '1') && (st[i] != '\0'))
{
i++;
k++;
}
if(k == 2)
{
st2[1][j] = '2';
}
else
{
st2[1][j] = '0';
}
st2[0][j] = st[i];
j++;
}
else
{
i++;
}
}
else if(st[i] == '0')
{
if(st[i+1] == '1')
{
i++;
while((st[i] != '0') && (st[i] != '\0'))
{
i++;
}
st2[1][j] = '0';
st2[0][j] = st[i];
j++;
}
else if(st[i+1] == '0')
{
while((st[i] != '1') && (st[i] != '\0'))
{
i++;
k++;
}
if(k == 2)
{
st2[1][j] = '2';
}
else
{
st2[1][j] = '0';
}
st2[0][j] = st[i];
j++;
}
else
{
i++;
}
}
}
//printf("%c %c %c\n", st2[0][j],st2[0][j-1],st2[0][j-2]);
//printf("%s\n", st2[0]);
st2[0][j] = '\0';
st2[1][j] = '\0';
if((st[0] == '1') && (st[i-1] == '1') && (st2[0][0] == '1') && (st2[0][1] == '\0'))
{
st2[0][0] = '0';
}
else if(st2[0][0] == '\0')
{
st2[0][0] = '1';
st2[0][1] = '\0';
}
else if(st2[0][j-1] == '\0')
{
j--;
if(st[i-1] == '0')
{
st2[0][j] = '1';
st2[1][j] = '0';
j++;
st2[0][j] = '\0';
st2[1][j] = '\0';
j++;
}
else
{
st2[0][j] = '0';
st2[1][j] = '0';
j++;
st2[0][j] = '\0';
st2[1][j] = '\0';
j++;
}
}
else
{
if(k == 2)
{
st2[0][j-1] = '0';
}
st2[0][j] = '0';
st2[1][j] = '0';
j++;
st2[0][j] = '\0';
st2[1][j] = '\0';
j++;
}
for(m = j;m>1;m--)
{
if((st2[0][m] == '0') && (st2[0][m-1] == '1') && (st2[1][m-1] == '2'))
{
st2[0][m-1] = '0';
}
}
//printf("%d\n", j);
printf("%s\n", st2[0]);
}
return 0;
}Binary String MEX CodeChef Solution in JAVA
/* package codechef; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
public static String Solve(String s, int n){
// int size = (int) 1e6;
int max0 = n;
int max1 = n;
int[] arr0 = new int[n];
int[] arr1 = new int[n];
int[] dp = new int[n+2];
int[] dp1 = new int[n+2];
for(int i=n-1;i>=0;i--){
if(s.charAt(i) == '0'){
max0 = i;
}
if(s.charAt(i) == '1'){
max1 = i;
}
arr0[i] = max0;
arr1[i] = max1;
}
if(max0 == n){
return "0";
}
if(max1 == n){
return "1";
}
// dp[n]= dp[n+1]=0;
// dp1[n]=dp1[n+1]=0;
for(int i=n-1;i>=0;--i) {
dp[i]=dp[i+1];
if(s.charAt(i)=='0'&& arr1[i]<n)
dp[i]=Math.max(dp[i], dp[arr1[i] + 1] + 1);
if(s.charAt(i)=='1'&& arr0[i]<n)
dp[i]=Math.max(dp[i], dp[arr0[i] + 1] + 1);
dp1[i]=dp1[i + 1];
if(arr1[i] < n) {
dp1[i]=Math.max(dp1[i], dp[arr1[i] + 1]+ 1);
}
}
// System.out.println(Arrays.toString(arr0)+" "+Arrays.toString(arr1)+" "+Arrays.toString(dp)+" "+Arrays.toString(dp1));
StringBuilder ans = new StringBuilder("1");
int len = dp1[0]+1;
// int index = 1;
int index=arr1[0]+1;
for(int i=1;i<len;i++){
if(index >=n){
ans.append("0");
continue;
}
if(arr0[index]>=n){
ans.append("0");
index = arr0[index]+1;
continue;
}
if(dp[arr0[index]+1] < (len-i-1)){
ans.append("0");
index = arr0[index]+1;
}else{
ans.append("1");
index = arr1[index]+1;
}
}
return ans.toString();
}
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
FastReader in = new FastReader();
int t = in.nextInt();
while((t--)>0){
String s = in.nextLine();
System.out.println(Solve(s, s.length()));
}
}
static class FastReader {
BufferedReader br;
StringTokenizer st;
public FastReader()
{
br = new BufferedReader(
new InputStreamReader(System.in));
}
String next()
{
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
}
catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() { return Integer.parseInt(next()); }
long nextLong() { return Long.parseLong(next()); }
double nextDouble()
{
return Double.parseDouble(next());
}
String nextLine()
{
String str = "";
try {
str = br.readLine();
}
catch (IOException e) {
e.printStackTrace();
}
return str;
}
}
}Binary String MEX CodeChef Solution in PYPY 3
from itertools import product
from sys import stdin, gettrace
if gettrace():
def inputi():
return input()
else:
def input():
return next(stdin)[:-1]
def inputi():
return stdin.buffer.readline()
# def is_subsequence(ss, tt):
# p = 0
# for s in ss:
# p = tt.find(s, p)+1
# if p == 0:
# return False
# return True
def solve(ss):
if '0' not in ss:
return '0'
if '1' not in ss:
return '1'
z = False
o = False
zoc = [0]
for s in ss[::-1]:
if s == '0':
z = True
else:
o = True
if z and o:
z = False
o = False
zoc.append(zoc[-1]+1)
else:
zoc.append(zoc[-1])
zoc = zoc[-2::-1]
p0 = 0
p1 = 0
pos = ss.find('1')
ln = zoc[pos]+1
res = ['1'] + ['0']*ln
for i in range(1, ln+1):
if p1 <= pos and p1 != -1:
p1 = ss.find('1', pos+1)
if p0 <= pos and p0 != -1:
p0 = ss.find('0', pos+1)
if p0 == -1:
res[i] = '0'
elif p1 == -1:
res[i] = '1'
elif zoc[p1] < zoc[p0]:
res[i] = '1'
pos = p1
else:
res[i] = '0'
pos = p0
return ''.join(res)
def main():
t = int(input())
for _ in range(t):
print(solve(input()))
# res = []
# for x in product('01', repeat=6):
# ss = ''.join(x)
# res.append((solve(ss), ss))
# res.sort()
# for r, ss in res:
# print(r, ss)
if __name__ == "__main__":
main()Binary String MEX CodeChef Solution in PYTH
dp, dp1 = [0] * 1000002, [0] * 1000002
n0, n1 = [0] * 1000000, [0] * 1000000
for _ in xrange(input()):
s = raw_input().strip()
n = len(s)
lp = -1
for i in xrange(n):
if s[i] == "0":
for j in xrange(lp+1, i+1):
n0[j] = i
lp = i
for i in xrange(lp+1, n):
n0[i] = n
if n0[0] == n:
print 0
continue
lp = -1
for i in xrange(n):
if s[i] == "1":
for j in xrange(lp+1, i+1):
n1[j] = i
lp = i
for i in xrange(lp+1, n):
n1[i] = n
dp[n] = dp[n+1] = 0
dp1[n] = dp1[n+1] = 0
for i in xrange(n-1, -1, -1):
dp[i] = dp[i+1]
if s[i] == "0" and n1[i] < n:
dp[i] = max(dp[i], dp[n1[i] + 1] + 1)
if s[i] == "1" and n0[i] < n:
dp[i] = max(dp[i], dp[n0[i] + 1] + 1)
dp1[i] = dp1[i+1]
if n1[i] < n:
dp1[i] = max(dp1[i], dp[n1[i] + 1] + 1)
o = dp1[0] + 1
ci = n1[0] + 1
ans = "1"
for i in xrange(1, o):
if ci >= n:
ans += "0"
continue
if n0[ci] >= n:
ans += "0"
ci = n0[ci] + 1
continue
if dp[n0[ci] + 1] < o - i - 1:
ans += "0"
ci = n0[ci] + 1
else:
ans += "1"
ci = n1[ci] + 1
print ansBinary String MEX CodeChef Solution in C#
using System;
using System.Text;
public class Test
{
static string FindMexString(string s)
{
int len = s.Length;
int index0 = -1;
int index1 = -1;
int[] indexOfZero = new int[len];
int[] indexOfOne = new int[len];
int[] dpOfZero = new int[len+2];
int[] dpofOne = new int[len+2];
//Find index of last '0' bit
for (int i = len-1; i >=0 ; i--)
{
if (s[i] == '0')
{
index0 = i;
break;
}
}
if (index0 == -1)
{
return "0";
}
else
{
for (int i=index0+1;i<len;i++)
{
indexOfZero[i] = len;
}
int j = index0;
for (int i = j; i >=0 ; i--)
{
indexOfZero[i] = index0;
if (s[i] == '0')
{
indexOfZero[i] = i;
index0 = i;
}
}
}
for (int i = len - 1; i >= 0; i--)
{
if (s[i] == '1')
{
index1 = i;
break;
}
}
if (index1 == -1)
{
return "1";
}
else
{
for (int i = index1 + 1; i < len; i++)
{
indexOfOne[i] = len;
}
int j = index1;
for (int i = j; i >= 0; i--)
{
indexOfOne[i] = index1;
if (s[i] == '1')
{
indexOfOne[i] = i;
index1 = i;
}
}
}
dpOfZero[len] = 0;
dpOfZero[len + 1] = 0;
dpofOne[len] = 0;
dpofOne[len + 1] = 0;
for (int i = len - 1; i >= 0; i--)
{
dpOfZero[i] = dpOfZero[i + 1];
if (s[i] == '0' && indexOfOne[i] < len)
{
dpOfZero[i] = Math.Max(dpOfZero[i], dpOfZero[indexOfOne[i] + 1] + 1);
}
if (s[i] == '1' && indexOfZero[i] < len)
{
dpOfZero[i] = Math.Max(dpOfZero[i], dpOfZero[indexOfZero[i] + 1] + 1);
}
dpofOne[i] = dpofOne[i + 1];
if (indexOfOne[i] < len)
{
dpofOne[i] = Math.Max(dpofOne[i], dpOfZero[indexOfOne[i] + 1] + 1);
}
}
int n = dpofOne[0] + 1;
int position = indexOfOne[0] + 1;
StringBuilder mex = new StringBuilder("1");
for (int i = 1; i < n; i++)
{
if (position >= len)
{
mex.Append('0');
continue;
}
if (indexOfZero[position] >= len)
{
mex.Append('0');
position = indexOfZero[position] + 1;
continue;
}
if (dpOfZero[indexOfZero[position] + 1] < n - i - 1)
{
mex.Append('0');
position = indexOfZero[position] + 1;
}
else
{
mex.Append('1');
position = indexOfOne[position] + 1;
}
}
return mex.ToString();
}
public static void Main()
{
int numOfTestCases = int.Parse(Console.ReadLine());
for (int i = 1; i <= numOfTestCases; i++)
{
string s = Console.ReadLine(); //Binary String
Console.WriteLine(FindMexString(s));
}
}
}Binary String MEX CodeChef Solution in GO
package main
import (
"bufio"
"bytes"
"fmt"
"os"
)
func main() {
reader := bufio.NewReader(os.Stdin)
tc := readNum(reader)
var buf bytes.Buffer
for tc > 0 {
tc--
s, _ := reader.ReadString('\n')
res := solve(len(s)-1, s)
buf.WriteString(res)
buf.WriteByte('\n')
}
fmt.Print(buf.String())
}
func readInt(bytes []byte, from int, val *int) int {
i := from
sign := 1
if bytes[i] == '-' {
sign = -1
i++
}
tmp := 0
for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
tmp = tmp*10 + int(bytes[i]-'0')
i++
}
*val = tmp * sign
return i
}
func readNum(reader *bufio.Reader) (a int) {
bs, _ := reader.ReadBytes('\n')
readInt(bs, 0, &a)
return
}
func readTwoNums(reader *bufio.Reader) (a int, b int) {
res := readNNums(reader, 2)
a, b = res[0], res[1]
return
}
func readThreeNums(reader *bufio.Reader) (a int, b int, c int) {
res := readNNums(reader, 3)
a, b, c = res[0], res[1], res[2]
return
}
func readNNums(reader *bufio.Reader, n int) []int {
res := make([]int, n)
x := 0
bs, _ := reader.ReadBytes('\n')
for i := 0; i < n; i++ {
for x < len(bs) && (bs[x] < '0' || bs[x] > '9') && bs[x] != '-' {
x++
}
x = readInt(bs, x, &res[i])
}
return res
}
func readUint64(bytes []byte, from int, val *uint64) int {
i := from
var tmp uint64
for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
tmp = tmp*10 + uint64(bytes[i]-'0')
i++
}
*val = tmp
return i
}
func solve(n int, s string) string {
nr := make([]Pair, n)
nr[n-1] = Pair{n, n}
for i := n - 2; i >= 0; i-- {
if s[i+1] == '0' {
nr[i] = Pair{i + 1, nr[i+1].second}
} else {
nr[i] = Pair{nr[i+1].first, i + 1}
}
}
if nr[0].first == n && s[0] != '0' {
// all 1
return "0"
}
if nr[0].second == n && s[0] != '1' {
// all 0
return "1"
}
dp := make([]int, n+1)
for i := n - 1; i >= 0; i-- {
dp[i] = min(dp[nr[i].first], dp[nr[i].second]) + 1
}
var pivot int
if s[0] != '1' {
pivot = nr[0].second
}
nb := dp[pivot] + 1
ans := make([]int, nb)
ans[0] = 1
for j := 1; j < nb; j++ {
nz := nr[pivot].first
if nz == n {
pivot = nz
continue
}
k := min(dp[nr[nz].first], dp[nr[nz].second])
if k == nb-j-1 {
ans[j] = 1
pivot = nr[pivot].second
} else {
ans[j] = 0
pivot = nz
}
}
var buf bytes.Buffer
for i := 0; i < len(ans); i++ {
buf.WriteByte(byte('0' + ans[i]))
}
return buf.String()
}
type Pair struct {
first, second int
}
func min(a, b int) int {
if a <= b {
return a
}
return b
}Binary String MEX CodeChef Solution Review:
In our experience, we suggest you solve this Binary String MEX CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.
If you are stuck anywhere between any coding problem, just visit Queslers to get the Binary String MEX CodeChef Solution.
Conclusion:
I hope this Binary String MEX CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.
This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.
Keep Learning!
