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


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("%d\n",x)
#define s(x) scanf("%lld",&x)
#define p(x) printf("%lld\n",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;
}