Divide binary array into three equal parts with same value
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 Code int 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 List def 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 ans arr = [ 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 Code int 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 approach import 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 Code public 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 Program A = [ 1 , 1 , 1 , 1 , 1 , 1 ] # Output required result print (ThreeEqualParts(A)) # This code is written by # Sanjit_Prasad |
C#
// C# implementation of the // above approach using 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 Code public 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 Program var A = [1, 1, 1, 1, 1, 1]; // Output required result console.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)