In this HackerEarth Three Equal parts problem solution You will be given a binary array A of length N. (Array filled with 0s and/or 1s)
You need to divide the array in three parts (that is , three subarrays) in such a way that all these parts represent the same value in decimal.
If it is possible to divide the array, output the common decimal value modulo 1000000007 else output -1.
See Sample test-case for better understanding.
Note – Here binary to decimal conversion is done using standard conversion method, i.e., right to left( Example – 1010 is 10 not 5).
HackerEarth Three Equal parts problem solution.
import java.util.*;
import java.io.*;
import java.lang.*;
import java.math.*;
import static java.lang.Math.*;
import java.util.concurrent.ThreadLocalRandom;
public class Sol implements Runnable {
long mod = (long)1e9 + 7;
long binaryToDecimal(String s) {
long pow[] = new long[s.length()];
pow[0] = 1;
for(int i=1;i<s.length();i++) {
pow[i] = pow[i - 1] * 2L;
pow[i] %= mod;
}
long ans = 0;
int power = 0;
for(int i=s.length()-1;i>=0;i--) {
if(s.charAt(i) == '1') {
ans += pow[power];
ans %= mod;
}
power++;
}
return ans;
}
void solve(InputReader in, PrintWriter w) {
int T = in.nextInt();
while(T-- > 0) {
int n = in.nextInt();
char c[] = new char[n];
for(int i=0;i<n;i++)
c[i] = in.next().charAt(0);
int count_1 = 0;
for(int i=0;i<n;i++)
if(c[i] == '1')
count_1++;
if(count_1 % 3 != 0)
System.out.println("-1");
else if(count_1 == 0)
System.out.println("0");
else {
StringBuilder str1 = new StringBuilder();
StringBuilder str2 = new StringBuilder();
StringBuilder str3 = new StringBuilder();
int zeroes1 = 0, zeroes2 = 0, zeroes3 = 0;
int ind = 0;
int ones = count_1 / 3;
// remove the leading zeroes..
while(ind < n && c[ind] != '1')
ind++;
// 1st part
int total1_1 = 0;
while(ind < n && total1_1 != ones) {
str1.append(c[ind]);
if(c[ind] == '1')
total1_1++;
ind++;
}
// count no of zeroes before the next '1'..
while(ind < n && c[ind] != '1') {
zeroes1++;
ind++;
}
// 2nd part
int total1_2 = 0;
while(ind < n && total1_2 != ones) {
str2.append(c[ind]);
if(c[ind] == '1')
total1_2++;
ind++;
}
// count no of zeroes before the next '1'..
while(ind < n && c[ind] != '1') {
zeroes2++;
ind++;
}
// 3rd part
int total1_3 = 0;
while(ind < n && total1_3 != ones) {
str3.append(c[ind]);
if(c[ind] == '1')
total1_3++;
ind++;
}
while(ind < n) {
zeroes3++;
ind++;
}
String val1 = str1.toString();
String val2 = str2.toString();
String val3 = str3.toString();
if(val1.equals(val2) && val2.equals(val3)) {
if(zeroes3 <= zeroes1 && zeroes3 <= zeroes2) {
for(int i=0;i<zeroes3;i++)
val3 += "0";
System.out.println(binaryToDecimal(val3));
}
else
System.out.println("-1");
}
// if not equal then print "-1"
else
System.out.println("-1");
}
}
}
// ************* Code ends here ***************
void init() throws Exception {
//Scanner in;
InputReader in;
PrintWriter w;
boolean online = false;
String common_in_fileName = "\in";
String common_out_fileName = "\out";
int test_files = 0;
for(int file_no = 0; file_no <= test_files; file_no++) {
String x = "" + file_no;
if (x.length() == 1) x = "0" + x;
String in_fileName = common_in_fileName + "" + x;
String out_fileName = common_out_fileName + "" + x;
if (online) {
//in = new Scanner(new File(in_fileName + ".txt"));
in = new InputReader(new FileInputStream(new File(in_fileName + ".txt")));
w = new PrintWriter(new FileWriter(out_fileName + ".txt"));
} else {
//in = new Scanner(System.in);
in = new InputReader(System.in);
w = new PrintWriter(System.out);
}
solve(in, w);
w.close();
}
}
public void run() {
try {
init();
}
catch(Exception e) {
System.out.println(e);
e.printStackTrace();
}
}
public static void main(String args[]) throws Exception {
new Thread(null, new Sol(),"Sol",1<<28).start();
}
static class InputReader {
private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
private SpaceCharFilter filter;
public InputReader(InputStream stream) {
this.stream = stream;
}
public int read() {
if (numChars == -1) {
throw new InputMismatchException();
}
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (numChars <= 0) {
return -1;
}
}
return buf[curChar++];
}
public String nextLine() {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = "";
try {
str = br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
return str;
}
public int nextInt() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
if (c < '0' || c > '9') {
throw new InputMismatchException();
}
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public long nextLong() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
if (c < '0' || c > '9') {
throw new InputMismatchException();
}
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public double nextDouble() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
double res = 0;
while (!isSpaceChar(c) && c != '.') {
if (c == 'e' || c == 'E') {
return res * Math.pow(10, nextInt());
}
if (c < '0' || c > '9') {
throw new InputMismatchException();
}
res *= 10;
res += c - '0';
c = read();
}
if (c == '.') {
c = read();
double m = 1;
while (!isSpaceChar(c)) {
if (c == 'e' || c == 'E') {
return res * Math.pow(10, nextInt());
}
if (c < '0' || c > '9') {
throw new InputMismatchException();
}
m /= 10;
res += (c - '0') * m;
c = read();
}
}
return res * sgn;
}
public String readString() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isSpaceChar(c));
return res.toString();
}
public boolean isSpaceChar(int c) {
if (filter != null) {
return filter.isSpaceChar(c);
}
return c == ' ' || c == 'n' || c == 'r' || c == 't' || c == -1;
}
public String next() {
return readString();
}
public interface SpaceCharFilter {
public boolean isSpaceChar(int ch);
}
}
}
Second solution
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define mp make_pair
#define pb push_back
#define si(x) scanf("%d",&x)
#define pi(x) printf("%dn",x)
#define s(x) scanf("%lld",&x)
#define p(x) printf("%lldn",x)
#define sc(x) scanf("%s",x)
#define pc(x) printf("%s",x)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define F first
#define S second
#define inf 4e18
#define prec(x) fixed<<setprecision(15)<<x
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define mem(x,y) memset(x,y,sizeof(x))
#define PQG priority_queue< int,std::vector<int>,std::greater<int> >
#define PQL priority_queue< int,std::vector<int>,std::less<int> >
#define PQPL priority_queue<pii ,vector< pii >, less< pii > >
#define PQPG priority_queue<pii ,vector< pii >, greater< pii > >
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
using namespace std;
const ll mod=1e9+7;
template <typename T>
T modpow(T base, T exp, T modulus) {
base %= modulus;
T result = 1;
while (exp > 0) {
if (exp & 1) result = (result * base) % modulus;
base = (base * base) % modulus;
exp >>= 1;
}
return result;
}
vector<int> zfunction(vector<int>s) {
int n=(int)s.size();
vector<int> z(n);
for(int i=1,l=0,r=0;i<n;i++) {
if(i<=r) z[i]=min(r-i+1,z[i-l]);
while(i+z[i]<n && s[z[i]]==s[i+z[i]]) z[i]++;
if(i+z[i]-1>r) l=i,r=i+z[i]-1;
}
return z;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
#endif
int t; cin>>t;
assert(t>=1 && t<=10);
while(t--) {
int n; cin>>n;
assert(n>=3 && n<=100000);
vector<int>ss;
int flag=0;
for(int i=0;i<n;i++) {
int x; cin>>x;
assert(x==0 || x==1);
if(x==1) flag=1;
if(!flag) continue;
ss.pb(x);
}
if(ss.size()==0) {
cout<<0<<endl;
continue;
}
n=ss.size();
vector<int>str;
for(int i=0;i<2*n;i++) {
str.pb(ss[i%n]);
}
vector<int>z=zfunction(str);
int idx[2*n+7];
idx[2*n]=2*n;
for(int i=2*n-1;i>=0;i--) {
idx[i]=idx[i+1];
if(str[i]==1) idx[i]=i;
}
int len=-1;
for(int i=1;i<=n;i++) {
int idx1=n;
int idx2=idx1+i;
if(idx2>2*n-1) break;
idx2=idx[idx2];
if(z[idx2]<i) continue;
int idx3=idx2+i;
if(idx3>2*n-1) break;
idx3=idx[idx3];
if(z[idx3]==i && idx3+i-1==2*n-1) {
len=i; break;
}
}
if(len==-1) cout<<-1<<endl;
else {
ll ans=0;
int pp=0;
for(int i=len-1;i>=0;i--) {
if(ss[i]==1) ans=ans+modpow(2LL,(ll)pp,mod);
pp++;
ans%=mod;
}
cout<<ans<<endl;
}
}
return 0;
}