Search

# Binary String MEX - CodeChef Solution in Java| AskTheCode

Updated: Apr 12

CodeChef April Long Challenge Solution | Binary String MEX (MEXSTR) solution | AskTheCode

Problem:

You are given a binary string S. Chef defines MEX(S) as the smallest non-negative integer such that its binary representation (without leading '0'-s; in particular, the binary representation of 0 is "0") is not a subsequence of S.

Chef is asking you to find MEX(S). Since this integer could be very large, find its binary representation (without leading '0'-s).

Input:

• The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.

• The first and only line of each test case contains a single string S.

Output:

For each test case, print a single line containing one string: MEX(S) in binary representation.

Example Input:

2 1001011 1111

Example Output:

1100 0

Explanation:

Example case 1: All integers between 0 and 11 inclusive, in binary representation, appear in S as subsequences. However, the binary representation of 12 (which is "1100") is not a subsequence of S.

Example case 2: Since S contains only '1'-s, the string "0" is not a subsequence of S and therefore MEX(S)=0.

Code:

```/* 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 void main(String[] args) {
Scanner sc=new Scanner(System.in);

int t=sc.nextInt();
while(t-->0){

String s=sc.next();
char str[]=new char[s.length()];
for(int i=0;i<str.length;i++) {
char c=s.charAt(i);
str[i] = c;
}
boolean lz=false;
int ind=0;
while (ind<str.length&&str[ind]=='0'){
lz=true;
ind++;

}
char str_new[]=new char[str.length-ind];
for(int i=ind;i<str.length;i++)
str_new[i-ind]=str[i];
String ans=mex(str_new);
if(ans.equals("10")) ans="0";
if(ans.equals("01")) ans="1";
if(ans.equals("0")&&lz) ans="10";
System.out.println(ans);
}
}
public static String mex(char s[]){
if(s.length==0) return "1";
if(s.length==1&&s=='0') return "1";
if(s.length==1&&s=='1') return "0";
int n=s.length;
int dp[][]=new int[n+2];
int l1i=n+1;
int l0i=n;
dp[n]=-1;
dp[n]=1;
dp[n+1]=-1;
dp[n+1]=1;
for(int i=n-1;i>=0;i--){
int ind=findmin(l0i,l1i,dp);
dp[i]=ind;
dp[i]=dp[ind]+1;
if(s[i]=='0') l0i=i;
else l1i=i;
}
int i=0;
StringBuffer sb=new StringBuffer("");
while(i!=-1){
if(i==n) sb.append('0');
else if(i==n+1) sb.append('1');
else sb.append(s[i]);
i=dp[i];
}
return sb.toString();
}
public static int findmin(int z,int o,int dp[][]){

return (dp[z]<=dp[o])?z:o;
}
}```

### Recent Posts

See All

#### Golf CodeChef Solution in Java - AskTheCode

CodeChef May Long Challenge Solution | Golf (LKDNGOLF) solution | AskTheCode Golf (LKDNGOLF) solution Problem: It's a lockdown. You’re bored in your house and are playing golf in the hallway. The hall

#### Solubility - CodeChef Solution in Java and C++| AskTheCode

CodeChef May Long Challenge Solution | Solubility (SOLBLTY) solution | AskTheCode Solubility (SOLBLTY) solution Problem: Suppose for a unit rise in temperature, the solubility of sugar in water increa

#### Valid Paths CodeChef Solution in C++ | AskTheCode

CodeChef May Long Challenge Solution | Valid Paths (VPATH) solution | AskTheCode Valid Paths (VPATH) CodeChef solution Problem: You are given a tree with N nodes numbered from 1 to N. A set S of nodes