Dada una array A de longitud n tal que contiene solo ‘ 0 s’ y ‘ 1 s’. La tarea es dividir la array en TRES partes diferentes no vacías de modo que todas estas partes representen el mismo valor binario (en decimales).
Si es posible, devuelve cualquier [i, j] con i+1 < j, tal que:
1. A[0], A[1], …, A[i] es la primera parte . 2. A[i+1], A[i+2], …, A[j-1] es la segunda parte . 3. A[j], A[j+1], …, A[n- 1] es la tercera parte . Nota: Las tres partes deben tener el mismo valor binario. Sin embargo, si no es posible, devuelve [-1, -1]. Ejemplos:
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]
Enfoque: digamos que el número total de unos en A sea S. Dado que cada parte tiene el mismo número de unos, todas las partes deben tener K = S / 3 unos. Si S no es divisible por 3 i:e S % 3 != 0 , entonces la tarea es imposible. Ahora vamos a encontrar la posición de la 1ra, K-ésima, K+1-ésima, 2K-ésima, 2K+1-ésima y 3K-ésima . Las posiciones de estos formarán 3 intervalos: [i1, j1], [i2, j2], [i3, j3] . (Si solo hay 3 unos, entonces los intervalos tienen una longitud de 1). Entre los intervalos, puede haber una cierta cantidad de ceros. Los ceros después del tercer intervalo j3 deben incluirse en cada parte: digamos que hay z de ellos (z = longitud de (S) – j3). Entonces la primera parte, [i1, j1] , ahora es [i1, j1+z] . Del mismo modo, la segunda parte,[i2, j2] , ahora es [i2, j2+z] . Si todo esto es realmente posible, entonces la respuesta final es [j1+z, j2+z+1] . A continuación se muestra la implementación del enfoque anterior.
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
Producción:
1 4
Complejidad temporal: O(N), donde N es la longitud de S. Complejidad espacial: O(N)
Publicación traducida automáticamente
Artículo escrito por Sanjit_Prasad y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA