Skip to content
Programming101
Programmingoneonone

Learn everything about programming

  • Home
  • CS Subjects
    • IoT – Internet of Things
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programming101
Programmingoneonone

Learn everything about programming

HackerEarth Three Equal parts problem solution

YASH PAL, 31 July 2024
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

Topics we are covering

Toggle
  • HackerEarth Three Equal parts problem solution.
    • Second 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("%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;
}
coding problems solutions

Post navigation

Previous post
Next post
  • Automating Image Format Conversion with Python: A Complete Guide
  • HackerRank Separate the Numbers solution
  • How AI Is Revolutionizing Personalized Learning in Schools
  • GTA 5 is the Game of the Year for 2024 and 2025
  • Hackerrank Day 5 loops 30 days of code solution
How to download udemy paid courses for free

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
  • YouTube
  • LinkedIn
  • Facebook
  • Pinterest
  • Instagram
©2025 Programmingoneonone | WordPress Theme by SuperbThemes