Dados tres números enteros N , E y O . La tarea es encontrar una array de tamaño N tal que el número de sub-arrays de suma par e impar sean E y O respectivamente.
Ejemplos:
Entrada: N = 3, E = 2, O = 4
Salida: 0 1 0
Hay un total de 6 subarrays: {0}, {1}, {0}, {0, 1}, {1, 0}, {0, 1, 0}.
Sus sumas son {0, 1, 0, 1, 1, 1} respectivamente.
2 de ellos son pares y 4 de ellos son impares.
Entrada: N = 3, E = 0, O = 6
Salida: -1
Enfoque ingenuo: use el enmascaramiento de bits para generar todas las combinaciones de 0 y 1 en la array. Para cada combinación calculamos el número de subarreglos de sumas pares e impares. Si son iguales a los valores dados, entonces es la combinación correcta e imprimimos
la array.
Para que este enfoque genere todos los conjuntos necesarios 
y para cada combinación, encontramos el número de subarreglos que cuestan 
.
Enfoque eficiente: como todos sabemos, PrefixSums de una array. Así que calcularemos el número de PrefixSum par y PrefixSum impar. Si de alguna manera conocemos el número de prefixSums que tienen paridad par e impar respectivamente, podemos crear correspondientemente cualquier array válida siempre que el recuento total de oddPrefixSums y evenPrefixSums sea N + 1.
Ejemplo:Si tenemos 3 evenPrefixSums y 2 oddPrefixSums, podemos crear una array [0, 0, 1, 0]. El truco consiste en colocar el único 1 después de colocar (evenPrefixSums – 1) ceros. Todos los prefixSums restantes obviamente serán de paridad impar.
La siguiente ecuación se cumple.
sumas de prefijos pares + sumas de prefijos impares = N + 1
Dado que prefixSum_i – prefixSum_j contribuye a las sumas de subconjuntos contiguos, ambos deben tener una paridad diferente. Por lo tanto, el número de subarreglos contiguos que tienen paridad impar será C(evenPrefixSums, 1) * C(oddPrefixSums, 1). Esto da lugar a otra ecuación.
sumas de prefijos pares * sumas de prefijos impares = O
Podemos formar una ecuación cuadrática y resolverla para obtener los valores respectivos. Si no encuentra ningún valor válido, envíe -1.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <algorithm>
#include <iostream>
using namespace std;
// Function to generate and print the required array
void CreateArray(int N, int even, int odd)
{
int temp = -1;
int OddPreSums;
// Find the number of odd prefix sums
for (int i = 0; i <= N + 1; i++) {
if (i * ((N + 1) - i) == odd) {
temp = 0;
OddPreSums = i;
break;
}
}
// If no odd prefix sum found
if (temp == -1) {
cout << temp << endl;
}
else {
// Calculating the number of even prefix sums
int EvenPreSums = (N + 1) - OddPreSums;
int e = 1;
int o = 0;
// Stores the current prefix sum
int CurrSum = 0;
for (int i = 0; i < N; i++) {
// If current prefix sum is even
if (CurrSum % 2 == 0) {
// Print 0 until e = EvenPreSums - 1
if (e < EvenPreSums) {
e++;
cout << "0 ";
}
else {
o++;
// Print 1 when e = EvenPreSums
cout << "1 ";
CurrSum++;
}
}
else {
if (e < EvenPreSums) {
e++;
cout << "1 ";
CurrSum++;
}
else {
o++;
// Print 0 for rest of the values
cout << "0 ";
}
}
}
cout << endl;
}
}
// Driver code
int main()
{
int N = 15;
int even = 60, odd = 60;
CreateArray(N, even, odd);
return 0;
}
Java
// Java implementation of the approach
import java.io.*;
class GFG {
// Function to generate and print the required array
static void CreateArray(int N, int even, int odd)
{
int EvenPreSums = 1;
int temp = -1;
int OddPreSums = 0;
// Find the number of odd prefix sums
for (int i = 0; i <= N + 1; i++) {
if (i * ((N + 1) - i) == odd) {
temp = 0;
OddPreSums = i;
break;
}
}
// If no odd prefix sum found
if (temp == -1) {
System.out.println(temp);
}
else {
// Calculating the number of even prefix sums
EvenPreSums = ((N + 1) - OddPreSums);
int e = 1;
int o = 0;
// Stores the current prefix sum
int CurrSum = 0;
for (int i = 0; i < N; i++) {
// If current prefix sum is even
if (CurrSum % 2 == 0) {
// Print 0 until e = EvenPreSums - 1
if (e < EvenPreSums) {
e++;
System.out.print("0 ");
}
else {
o++;
// Print 1 when e = EvenPreSums
System.out.print("1 ");
CurrSum++;
}
}
else {
if (e < EvenPreSums) {
e++;
System.out.print("1 ");
CurrSum++;
}
else {
o++;
// Print 0 for rest of the values
System.out.print("0 ");
}
}
}
System.out.println();
}
}
// Driver code
public static void main(String[] args)
{
int N = 15;
int even = 60, odd = 60;
CreateArray(N, even, odd);
}
}
// This code is contributed by akt_mit
Python3
# Python 3 implementation of the approach
# Function to generate and print
# the required array
def CreateArray(N, even, odd):
temp = -1
# Find the number of odd prefix sums
for i in range(N + 2):
if (i * ((N + 1) - i) == odd):
temp = 0
OddPreSums = i
break
# If no odd prefix sum found
if (temp == -1):
print(temp)
else:
# Calculating the number
# of even prefix sums
EvenPreSums = (N + 1) - OddPreSums
e = 1
o = 0
# Stores the current prefix sum
CurrSum = 0
for i in range(N):
# If current prefix sum is even
if (CurrSum % 2 == 0):
# Print 0 until e = EvenPreSums - 1
if (e < EvenPreSums):
e += 1
print("0 ", end = "")
else:
o += 1
# Print 1 when e = EvenPreSums
print("1 ", end = "")
CurrSum += 1
else:
if (e < EvenPreSums):
e += 1
print("1 ")
CurrSum += 1
else:
o += 1
# Print 0 for rest of the values
print("0 ", end = "")
print("\n", end = "")
# Driver code
if __name__ == '__main__':
N = 15
even = 60
odd = 60
CreateArray(N, even, odd)
# This code is contributed by
# Surendra_Gangwar
C#
// C# implementation of the approach
using System;
class GFG {
// Function to generate and print the required array
static void CreateArray(int N, int even, int odd)
{
int EvenPreSums = 1;
int temp = -1;
int OddPreSums = 0;
// Find the number of odd prefix sums
for (int i = 0; i <= N + 1; i++) {
if (i * ((N + 1) - i) == odd) {
temp = 0;
OddPreSums = i;
break;
}
}
// If no odd prefix sum found
if (temp == -1) {
Console.WriteLine(temp);
}
else {
// Calculating the number of even prefix sums
EvenPreSums = ((N + 1) - OddPreSums);
int e = 1;
int o = 0;
// Stores the current prefix sum
int CurrSum = 0;
for (int i = 0; i < N; i++) {
// If current prefix sum is even
if (CurrSum % 2 == 0) {
// Print 0 until e = EvenPreSums - 1
if (e < EvenPreSums) {
e++;
Console.Write("0 ");
}
else {
o++;
// Print 1 when e = EvenPreSums
Console.Write("1 ");
CurrSum++;
}
}
else {
if (e < EvenPreSums) {
e++;
Console.Write("1 ");
CurrSum++;
}
else {
o++;
// Print 0 for rest of the values
Console.Write("0 ");
}
}
}
Console.WriteLine();
}
}
// Driver code
static public void Main()
{
int N = 15;
int even = 60, odd = 60;
CreateArray(N, even, odd);
}
}
// This code is contributed by Tushil
PHP
<?php
// PHP implementation of the approach
// Function to generate and print the required array
function CreateArray($N, $even, $odd)
{
$temp = -1;
$OddPreSums = 0;
// Find the number of odd prefix sums
for ($i = 0; $i <= $N + 1; $i++)
{
if ($i * (($N + 1) - $i) == $odd)
{
$temp = 0;
$OddPreSums = $i;
break;
}
}
// If no odd prefix sum found
if ($temp == -1)
{
echo temp ;
}
else
{
// Calculating the number of even prefix sums
$EvenPreSums = ($N + 1) - $OddPreSums;
$e = 1;
$o = 0;
// Stores the current prefix sum
$CurrSum = 0;
for ($i = 0; $i < $N; $i++)
{
// If current prefix sum is even
if ($CurrSum % 2 == 0)
{
// Print 0 until e = EvenPreSums - 1
if ($e < $EvenPreSums)
{
$e++;
echo "0 ";
}
else
{
$o++;
// Print 1 when e = EvenPreSums
echo "1 ";
$CurrSum++;
}
}
else
{
if ($e < $EvenPreSums)
{
$e++;
echo "1 ";
$CurrSum++;
}
else
{
$o++;
// Print 0 for rest of the values
echo "0 ";
}
}
}
echo "\n";
}
}
// Driver code
$N = 15;
$even = 60;
$odd = 60;
CreateArray($N, $even, $odd);
// This code is contributed by AnkitRai01
?>
Javascript
<script>
// Javascript implementation of the approach
// Function to generate and print the required array
function CreateArray(N, even, odd)
{
let EvenPreSums = 1;
let temp = -1;
let OddPreSums = 0;
// Find the number of odd prefix sums
for (let i = 0; i <= N + 1; i++) {
if (i * ((N + 1) - i) == odd) {
temp = 0;
OddPreSums = i;
break;
}
}
// If no odd prefix sum found
if (temp == -1) {
document.write(temp);
}
else {
// Calculating the number of even prefix sums
EvenPreSums = ((N + 1) - OddPreSums);
let e = 1;
let o = 0;
// Stores the current prefix sum
let CurrSum = 0;
for (let i = 0; i < N; i++) {
// If current prefix sum is even
if (CurrSum % 2 == 0) {
// Print 0 until e = EvenPreSums - 1
if (e < EvenPreSums) {
e++;
document.write("0 ");
}
else {
o++;
// Print 1 when e = EvenPreSums
document.write("1 ");
CurrSum++;
}
}
else {
if (e < EvenPreSums) {
e++;
document.write("1 ");
CurrSum++;
}
else {
o++;
// Print 0 for rest of the values
document.write("0 ");
}
}
}
document.write();
}
}
let N = 15;
let even = 60, odd = 60;
CreateArray(N, even, odd);
</script>
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
Complejidad de tiempo: O(N), para iterar sobre la array
Espacio auxiliar: O(1), ya que no se requiere espacio adicional
Publicación traducida automáticamente
Artículo escrito por sharadgoyal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA