Generate an Array in which count of even and odd sum sub-arrays are E and O respectively

0 0 7 minutes read

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 $O(2^N)$ and for each combination, we find number of sub-arrays costing $O(2^N * N^2)$ .
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 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>

Output:

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

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!