Given an array A of length n such that it contains only ‘0s’ and ‘1s’. The task is to divide the array into THREE different non-empty parts such that all of these parts represent the same binary value(in decimals).
If it is possible, return any [i, j] with i+1 < j, such that:
- A[0], A[1], …, A[i] is the first part.
- A[i+1], A[i+2], …, A[j-1] is the second part.
- A[j], A[j+1], …, A[n- 1] is the third part. Note: All three parts should have equal binary values. However, If it is not possible, return [-1, -1].
Examples:
Input : A = [1, 1, 1, 1, 1, 1] Output : [1, 4] All three parts are, A[0] to A[1] first part, A[2] to A[3] second part, A[4] to A[5] third part. Input : A = [1, 0, 0, 1, 0, 1] Output : [0, 4]
Naive Approach
The idea is to find every possible index pair i and j with i+1<j to divide the array into three parts. Then find the decimal value of each part and if the decimal value of all three parts are equal then return/print that i and j.
Steps to implement-
- Find the size of the input array/vector
- Declare a vector to store the final answer
- Now run two nested for loops to choose index i and j with i+1<j such that we will get three parts of array
- After that initialize three variables with a value of 0 to find the decimal value of those three parts
- Run a for loop from i to 0 to find the decimal value of the first part
- Run a for loop from j-1 to i+1 to find the decimal value of the second part
- Run a for loop from N-1 to j to find the decimal value of the third part
- When decimal value of all three part becomes equal then print or return i,j value
- In last if nothing got printed or returned then print or return -1,-1
Code
C++
// C++ implementation of the // above approach#include <bits/stdc++.h>using namespace std;// Function to return required // interval answer.vector<int> ThreeEqualParts(vector<int> arr){ //Size of input vector int N=arr.size(); //To store answer vector<int> ans; //Check for different possible i,j for(int i=0;i<N-2;i++){ for(int j=i+2;j<N;j++){ //Initialize decimal value of all three part to zero int val1=0; int val2=0; int val3=0; int temp; //Finding decimal value of first part temp=1; for(int k=i;k>=0;k--){ val1+=temp*arr[k]; temp=temp*2; } //Finding decimal value of second part temp=1; for(int k=j-1;k>=i+1;k--){ val2+=temp*arr[k]; temp=temp*2; } //Finding decimal value of third part temp=1; for(int k=N-1;k>=j;k--){ val3+=temp*arr[k]; temp=temp*2; } //When all three part has equal value if(val1==val2 && val2==val3 && val1==val3){ ans.push_back(i); ans.push_back(j); return ans; } } } //If no such value is possible then //we need to return [-1,-1] ans.push_back(-1); ans.push_back(-1); return ans;}// Driver Codeint main(){ vector<int> arr = {1, 1, 1, 1, 1, 1}; // Output required result vector<int> res = ThreeEqualParts(arr); for(auto it :res) cout << it << " "; return 0;} |
Java
import java.util.ArrayList;import java.util.List;public class Main { public static List<Integer> threeEqualParts(List<Integer> arr) { int N = arr.size(); List<Integer> ans = new ArrayList<>(); for (int i = 0; i < N - 2; i++) { for (int j = i + 2; j < N; j++) { int val1 = 0, val2 = 0, val3 = 0; int temp; for (int k = i; k >= 0; k--) { temp = (int) Math.pow(2, i - k); val1 += arr.get(k) * temp; } for (int k = j - 1; k >= i + 1; k--) { temp = (int) Math.pow(2, j - k - 1); val2 += arr.get(k) * temp; } for (int k = N - 1; k >= j; k--) { temp = (int) Math.pow(2, N - 1 - k); val3 += arr.get(k) * temp; } if (val1 == val2 && val2 == val3 && val1 == val3) { ans.add(i); ans.add(j); return ans; } } } ans.add(-1); ans.add(-1); return ans; } public static void main(String[] args) { List<Integer> arr = List.of(1, 1, 1, 1, 1, 1); List<Integer> res = threeEqualParts(arr); System.out.println(res); }} |
Python3
from typing import Listdef threeEqualParts(arr: List[int]) -> List[int]: N = len(arr) ans = [] for i in range(N - 2): for j in range(i + 2, N): val1, val2, val3 = 0, 0, 0 temp = 1 for k in range(i, -1, -1): val1 += arr[k] * temp temp *= 2 temp = 1 for k in range(j - 1, i, -1): val2 += arr[k] * temp temp *= 2 temp = 1 for k in range(N - 1, j - 1, -1): val3 += arr[k] * temp temp *= 2 if val1 == val2 == val3: ans.append(i) ans.append(j) return ans ans.append(-1) ans.append(-1) return ansarr = [1, 1, 1, 1, 1, 1]res = threeEqualParts(arr)print(res) |
C#
using System;using System.Collections.Generic;public class ThreeEqualParts { public static List<int> FindEqualParts(List<int> arr) { int N = arr.Count; List<int> ans = new List<int>(); for(int i=0; i<N-2; i++) { for(int j=i+2; j<N; j++) { int val1=0, val2=0, val3=0; int temp; for(int k=i; k>=0; k--) { val1 += arr[k] * (int)Math.Pow(2, i-k); } for(int k=j-1; k>=i+1; k--) { val2 += arr[k] * (int)Math.Pow(2, j-1-k); } for(int k=N-1; k>=j; k--) { val3 += arr[k] * (int)Math.Pow(2, N-1-k); } if(val1 == val2 && val2 == val3) { ans.Add(i); ans.Add(j); return ans; } } } ans.Add(-1); ans.Add(-1); return ans; } public static void Main() { List<int> arr = new List<int> {1, 1, 1, 1, 1, 1}; List<int> res = FindEqualParts(arr); foreach(int it in res) { Console.Write(it + " "); } }} |
PHP
<?php function threeEqualParts($arr) { // Size of input array $N = count($arr); // To store answer $ans = array(); // Check for different possible i, j for ($i = 0; $i < $N - 2; $i++) { for ($j = $i + 2; $j < $N; $j++) { // Initialize decimal value of all three part to zero $val1 = 0; $val2 = 0; $val3 = 0; $temp; // Finding decimal value of first part $temp = 1; for ($k = $i; $k >= 0; $k--) { $val1 += $temp * $arr[$k]; $temp *= 2; } // Finding decimal value of second part $temp = 1; for ($k = $j - 1; $k >= $i + 1; $k--) { $val2 += $temp * $arr[$k]; $temp *= 2; } // Finding decimal value of third part $temp = 1; for ($k = $N - 1; $k >= $j; $k--) { $val3 += $temp * $arr[$k]; $temp *= 2; } // When all three part has equal value if ($val1 == $val2 && $val2 == $val3 && $val1 == $val3) { array_push($ans, $i); array_push($ans, $j); return $ans; } } } // If no such value is possible then // we need to return [-1,-1] array_push($ans, -1); array_push($ans, -1); return $ans;}// Driver code$arr = array(1, 1, 1, 1, 1, 1); // Output required result$res = threeEqualParts($arr); foreach ($res as $it) echo $it . " ";?> |
Javascript
function findEqualParts(arr) { const N = arr.length; const ans = []; for(let i=0; i<N-2; i++) { for(let j=i+2; j<N; j++) { let val1=0, val2=0, val3=0; let temp; for(let k=i; k>=0; k--) { val1 += arr[k] * Math.pow(2, i-k); } for(let k=j-1; k>=i+1; k--) { val2 += arr[k] * Math.pow(2, j-1-k); } for(let k=N-1; k>=j; k--) { val3 += arr[k] * Math.pow(2, N-1-k); } if(val1 === val2 && val2 === val3) { ans.push(i); ans.push(j); return ans; } } } ans.push(-1); ans.push(-1); return ans;}const arr = [1, 1, 1, 1, 1, 1];const res = findEqualParts(arr);console.log(res); |
1 4
Time Complexity: O(N3), because of two nested loops to find i and j, and then loops to find the decimal value of all three parts
Auxiliary Space: O(1), because no extra space has been used
Another Approach:
Lets say total number of ones in A be S. Since every part has the same number of ones, thus all parts should have K = S / 3 ones. If S isn’t divisible by 3 i:e S % 3 != 0, then the task is impossible. Now we will find the position of the 1st, K-th, K+1-th, 2K-th, 2K+1-th, and 3K-th one. The positions of these ones will form 3 intervals: [i1, j1], [i2, j2], [i3, j3]. (If there are only 3 ones, then the intervals are each length 1.) Between the intervals, there may be some number of zeros.
The zeros after third interval j3 must be included in each part: say there are z of them (z = length of (S) – j3). So the first part, [i1, j1], is now [i1, j1+z]. Similarly, the second part, [i2, j2], is now [i2, j2+z]. If all this is actually possible, then the final answer is [j1+z, j2+z+1].
Below is the implementation of above approach.
C++
// C++ implementation of the // above approach#include <bits/stdc++.h>using namespace std;// Function to return required // interval answer.vector<int> ThreeEqualParts(vector<int> A){ int imp[] = {-1, -1}; vector<int> IMP(imp, imp + 2); // Finding total number of ones int Sum = accumulate(A.begin(), A.end(), 0); if (Sum % 3) { return IMP; } int K = Sum / 3; // Array contains all zeros. if (K == 0) { return {0, (int)A.size() - 1}; } vector<int> interval; int S = 0; for (int i = 0 ;i < A.size(); i++) { int x = A[i]; if (x) { S += x; if (S == 1 or S == K + 1 or S == 2 * K + 1) { interval.push_back(i); } if (S == K or S == 2 * K or S == 3 * K) { interval.push_back(i); } } } int i1 = interval[0], j1 = interval[1], i2 = interval[2], j2 = interval[3], i3 = interval[4], j3 = interval[5]; vector<int> a(A.begin() + i1, A.begin() + j1 + 1); vector<int> b(A.begin() + i2, A.begin() + j2 + 1); vector<int> c(A.begin() + i3, A.begin() + j3 + 1); // The array is in the form // W [i1, j1] X [i2, j2] Y [i3, j3] Z // where [i1, j1] is a block of 1s, and so on. if (!((a == b) and (b == c))) { return {-1, -1}; } // x, y, z: the number of zeros // after part 1, 2, 3 int x = i2 - j1 - 1; int y = i3 - j2 - 1; int z = A.size() - j3 - 1; if (x < z or y < z) { return IMP; } // appending extra zeros at end of // first and second interval j1 += z; j2 += z; return {j1, j2 + 1}; }// Driver Codeint main(){ vector<int> A = {1, 1, 1, 1, 1, 1}; // Output required result vector<int> res = ThreeEqualParts(A); for(auto it :res) cout << it << " "; return 0;}// This code is contributed // by Harshit Saini |
Java
// Java implementation of the // above approachimport java.util.*;class GFG{// Function to return required // interval answer.public static int[] ThreeEqualParts(int[] A){ int IMP[] = new int[]{-1, -1}; // Finding total number of ones int Sum = Arrays.stream(A).sum(); if ((Sum % 3) != 0) { return IMP; } int K = Sum / 3; // Array contains all zeros. if (K == 0) { return new int[]{0, A.length - 1}; } ArrayList<Integer> interval = new ArrayList<Integer>(); int S = 0; for (int i = 0 ;i < A.length; i++) { int x = A[i]; if (x != 0) { S += x; if ((S == 1) || (S == K + 1) || (S == 2 * K + 1)) { interval.add(i); } if ((S == K) || (S == 2 * K) || (S == 3 * K)) { interval.add(i); } } } int i1 = interval.get(0), j1 = interval.get(1), i2 = interval.get(2), j2 = interval.get(3), i3 = interval.get(4), j3 = interval.get(5); int [] a = Arrays.copyOfRange(A, i1, j1 + 1); int [] b = Arrays.copyOfRange(A, i2, j2 + 1); int [] c = Arrays.copyOfRange(A, i3, j3 + 1); // The array is in the form // W [i1, j1] X [i2, j2] Y [i3, j3] Z // where [i1, j1] is a block of 1s, and so on. if (!(Arrays.equals(a, b) && Arrays.equals(b, c))) { return new int[]{-1, -1}; } // x, y, z: // the number of zeros after part 1, 2, 3 int x = i2 - j1 - 1; int y = i3 - j2 - 1; int z = A.length - j3 - 1; if (x < z || y < z) { return IMP; } // appending extra zeros at end // of first and second interval j1 += z; j2 += z; return new int[]{j1, j2 + 1}; }// Driver Codepublic static void main(String []args){ int[] A = new int[]{1, 1, 1, 1, 1, 1}; // Output required result int[] res = ThreeEqualParts(A); System.out.println(Arrays.toString(res));}}// This code is contributed // by Harshit Saini |
Python3
# Python implementation of the above approach# Function to return required interval answer.def ThreeEqualParts(A): IMP = [-1, -1] # Finding total number of ones Sum = sum(A) if Sum % 3: return IMP K = Sum / 3 # Array contains all zeros. if K == 0: return [0, len(A) - 1] interval = [] S = 0 for i, x in enumerate(A): if x: S += x if S in {1, K + 1, 2 * K + 1}: interval.append(i) if S in {K, 2 * K, 3 * K}: interval.append(i) i1, j1, i2, j2, i3, j3 = interval # The array is in the form W [i1, j1] X [i2, j2] Y [i3, j3] Z # where [i1, j1] is a block of 1s, and so on. if not(A[i1:j1 + 1] == A[i2:j2 + 1] == A[i3:j3 + 1]): return [-1, -1] # x, y, z: the number of zeros after part 1, 2, 3 x = i2 - j1 - 1 y = i3 - j2 - 1 z = len(A) - j3 - 1 if x < z or y < z: return IMP # appending extra zeros at end of first and second interval j1 += z j2 += z return [j1, j2 + 1]# Driver ProgramA = [1, 1, 1, 1, 1, 1]# Output required resultprint(ThreeEqualParts(A))# This code is written by# Sanjit_Prasad |
C#
// C# implementation of the // above approachusing System;using System.Linq;using System.Collections.Generic;class GFG{// Function to return required// interval answer.static int[] ThreeEqualParts(int[] A){ int []IMP = new int[]{-1, -1}; // Finding total number of ones int Sum = A.Sum(); if ((Sum % 3) != 0) { return IMP; } int K = Sum / 3; // Array contains all zeros. if (K == 0) { return new int[]{0, A.Length - 1}; } List<int> interval = new List<int>(); int S = 0; for (int i = 0 ;i < A.Length; i++) { int x = A[i]; if (x != 0) { S += x; if ((S == 1) || (S == K + 1) || (S == 2 * K + 1)) { interval.Add(i); } if ((S == K) || (S == 2 * K) || (S == 3 * K)) { interval.Add(i); } } } int i1 = interval[0], j1 = interval[1], i2 = interval[2], j2 = interval[3], i3 = interval[4], j3 = interval[5]; var a = A.Skip(i1).Take(j1 - i1 + 1).ToArray(); var b = A.Skip(i2).Take(j2 - i2 + 1).ToArray(); var c = A.Skip(i3).Take(j3 - i3 + 1).ToArray(); // The array is in the form // W [i1, j1] X [i2, j2] Y [i3, j3] Z // where [i1, j1] is a block of 1s, // and so on. if (!(Enumerable.SequenceEqual(a,b) && Enumerable.SequenceEqual(b,c))) { return new int[]{-1, -1}; } // x, y, z: the number of zeros // after part 1, 2, 3 int X = i2 - j1 - 1; int y = i3 - j2 - 1; int z = A.Length - j3 - 1; if (X < z || y < z) { return IMP; } // appending extra zeros at end // of first and second interval j1 += z; j2 += z; return new int[]{j1, j2 + 1}; }// Driver Codepublic static void Main(){ int[] A = new int[]{1, 1, 1, 1, 1, 1}; // Output required result int[] res = ThreeEqualParts(A); Console.WriteLine(string.Join(" ", res));}}// This code is contributed // by Harshit Saini |
PHP
<?php// PHP implementation of the// above approach// Function to return required // interval answer.function ThreeEqualParts($A){ $IMP = array(-1, -1); // Finding total number of ones $Sum = array_sum($A); if ($Sum % 3) { return $IMP; } $K = $Sum / 3; // Array contains all zeros. if ($K == 0) { return array(0, count(A, COUNT_NORMAL) - 1); } $interval = array(); $S = 0; for ($i = 0; $i < count($A, COUNT_NORMAL); $i++) { $x = $A[$i]; if ($x) { $S += $x; if ($S == 1 or $S == $K + 1 or $S == 2 * $K + 1) { array_push($interval,$i); } if ($S == $K or $S == 2 * $K or $S == 3 * $K) { array_push($interval, $i); } } } $i1 = $interval[0]; $j1 = $interval[1]; $i2 = $interval[2]; $j2 = $interval[3]; $i3 = $interval[4]; $j3 = $interval[5]; $a = array_slice($A, $i1, $j1 - $i1 + 1); $b = array_slice($A, $i1, $j2 - $i2 + 1); $c = array_slice($A, $i1, $j3 - $i3 + 1); // The array is in the form // W [i1, j1] X [i2, j2] Y [i3, j3] Z // where [i1, j1] is a block of 1s, // and so on. if (!($a == $b and $b == $c)) { return array(-1, -1); } // x, y, z: the number of zeros // after part 1, 2, 3 $x = $i2 - $j1 - 1; $y = $i3 - $j2 - 1; $z = count($A) - $j3 - 1; if ($x < $z or $y < $z) { return $IMP; } // appending extra zeros at end // of first and second interval $j1 += $z; $j2 += $z; return array($j1, $j2 + 1); }// Driver Code$A = array(1, 1, 1, 1, 1, 1); // Output required result$res = ThreeEqualParts($A);foreach ($res as $key => $value) { echo $value." ";}// This code is contributed // by Harshit Saini ?> |
Javascript
//JavaScript implementation of the above approach//function to compare two arrays function isEqual(a, b) { // If length is not equal if(a.length!=b.length) return false; else { // Comparing each element of array for(var i=0;i<a.length;i++) if(a[i]!=b[i]) return false; return true; } }// Function to return required interval answer.function ThreeEqualParts(A){ var IMP = [-1, -1]; // Finding total number of ones var Sum = A.reduce(function (x, y) { return x + y; }, 0); if (Sum % 3 > 0) return IMP; var K = Sum / 3; // Array contains all zeros. if (K == 0) return [0, A.length - 1]; var interval = []; var S = 0; for (var i = 0; i < A.length; i++) { x = A[i]; if (x) { S += x; if (S == 1 || S == K + 1 || S == 2 * K + 1) interval.push(i); if (S == K || S == 2 * K || S == 3 * K) interval.push(i); } } var i1 = interval[0]; var j1 = interval[1]; var i2 = interval[2]; var j2 = interval[3]; var i3 = interval[4]; var j3 = interval[5]; // The array is in the form W [i1, j1] X [i2, j2] Y [i3, j3] Z // where [i1, j1] is a block of 1s, and so on. if (!(isEqual(A.slice(i1, j1 + 1), A.slice(i2, j2 + 1)) || isEqual(A.slice(i2, j2 + 1), A.slice(i3,j3 + 1)))) return [-1, -1]; // x, y, z: the number of zeros after part 1, 2, 3 var x = i2 - j1 - 1; var y = i3 - j2 - 1; var z = A.length - j3 - 1; if (x < z || y < z) return IMP; // appending extra zeros at end of first and second interval j1 += z; j2 += z; return [j1, j2 + 1];}// Driver Programvar A = [1, 1, 1, 1, 1, 1];// Output required resultconsole.log(ThreeEqualParts(A));// This code is written by phasing17 |
1 4
Complexity Analysis:
- Time Complexity: O(N), where N is the length of S.
- Space Complexity: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
