Given three integers N, E and O. The task is to find an array of size N such that the number of sub-arrays of sum even and odd are E and O respectively.
Examples:
Input: N = 3, E = 2, O = 4
Output: 0 1 0
There are total 6 sub-arrays: {0}, {1}, {0}, {0, 1}, {1, 0}, {0, 1, 0}.
Their sums are {0, 1, 0, 1, 1, 1} respectively.
2 of them are even and 4 of them are odd.
Input: N = 3, E = 0, O = 6
Output: -1
Naive approach: Use bitmasking to generate all combinations of 0’s and 1’s in the array. For every combination we calculate the number of even sum and odd sum sub-arrays. If they are equal to the given values then it is the right combination and we print
the array.
For this approach to generate all the sets it would take 
and for each combination, we find number of sub-arrays costing 
.
Efficient approach: As we all know about PrefixSums of an array. So We will calculate the number of even PrefixSum and odd PrefixSum. If we somehow know the number of prefixSums having odd and even parity respectively, we can correspondingly create any valid array provided that total count of oddPrefixSums and evenPrefixSums is N + 1.
Example: If we have 3 evenPrefixSums and 2 oddPrefixSums, we can create an array [0, 0, 1, 0]. The trick is to place the only 1 after placing (evenPrefixSums – 1) zeros. All the remaining prefixSums will obviously be of odd parity.
The following equation holds true.
evenPrefixSums + oddPrefixSums = N + 1
Since, prefixSum_i – prefixSum_j contributes to sums of contiguous sub-arrays, both should be of different parity. Hence, number of contiguous sub-arrays having odd parity will be C(evenPrefixSums, 1) * C(oddPrefixSums, 1). This gives rise to another equation.
evenPrefixSums * oddPrefixSums = O
We can form a quadratic equation and solve it to get the respective values. If you do not find any valid values, output -1.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <algorithm>#include <iostream>using namespace std;// Function to generate and print the required arrayvoid 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 codeint main(){ int N = 15; int even = 60, odd = 60; CreateArray(N, even, odd); return 0;} |
Java
// Java implementation of the approachimport 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 arraydef 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 codeif __name__ == '__main__': N = 15 even = 60 odd = 60 CreateArray(N, even, odd)# This code is contributed by# Surendra_Gangwar |
C#
// C# implementation of the approachusing 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
Time Complexity: O(N), to iterate over the array
Auxiliary Space: O(1), as no extra space is required
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
