# HackerEarth Three Equal parts problem solution

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("%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;}