Рубрики

Создайте массив, в котором подсчет четных и нечетных подмассивов равен E и O соответственно

Даны три целых числа N , E и O. Задача состоит в том, чтобы найти массив размера N, такой, чтобы количество подмассивов суммы четных и нечетных равнялось E и O соответственно.

Примеры:

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

Наивный подход: использовать битовую маску для генерации всех комбинаций 0 и 1 в массиве. Для каждой комбинации мы вычисляем количество подмассивов четной суммы и нечетной суммы. Если они равны заданным значениям, то это правильная комбинация, и мы печатаем
массив.
Для этого подхода сгенерировать все наборы, которые потребуются и для каждой комбинации мы находим количество подмассивов стоимостью ,

Эффективный подход: как мы все знаем о PrefixSums массива. Поэтому мы рассчитаем количество четных PrefixSum и нечетных PrefixSum. Если мы каким-то образом знаем количество префиксных сумм, имеющих нечетную и четную четность соответственно, мы можем соответственно создать любой допустимый массив при условии, что общее количество oddPrefixSums и evenPrefixSums равно N + 1.

Пример: если у нас есть 3 evenPrefixSums и 2 oddPrefixSums, мы можем создать массив [0, 0, 1, 0]. Хитрость заключается в том, чтобы поместить только 1 после размещения (evenPrefixSums — 1) нулей. Все оставшиеся префиксные суммы, очевидно, будут иметь нечетную четность.

Следующее уравнение верно.

evenPrefixSums + oddPrefixSums = N + 1

Поскольку prefixSum_i — prefixSum_j вносит вклад в суммы смежных подмассивов, оба должны иметь разную четность. Следовательно, число смежных подмассивов, имеющих нечетную четность, будет C (evenPrefixSums, 1) * C (oddPrefixSums, 1). Это приводит к другому уравнению.

evenPrefixSums * oddPrefixSums = O

Мы можем сформировать квадратное уравнение и решить его, чтобы получить соответствующие значения. Если вы не найдете никаких допустимых значений, выведите -1.

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ реализация подхода
#include <algorithm>
#include <iostream>

using namespace std;

  
// Функция для генерации и печати необходимого массива

void CreateArray(int N, int even, int odd)

{

    int temp = -1;

    int OddPreSums;

  

    // Находим количество нечетных сумм префиксов

    for (int i = 0; i <= N + 1; i++) {

        if (i * ((N + 1) - i) == odd) {

            temp = 0;

            OddPreSums = i;

            break;

        }

    }

  

    // Если не найдена нечетная префиксная сумма

    if (temp == -1) {

        cout << temp << endl;

    }

    else {

  

        // Расчет количества четных префиксных сумм

        int EvenPreSums = (N + 1) - OddPreSums;

        int e = 1;

        int o = 0;

  

        // Сохраняет текущую сумму префикса

        int CurrSum = 0;

        for (int i = 0; i < N; i++) {

  

            // Если текущая сумма префикса четна

            if (CurrSum % 2 == 0) {

  

                // печатаем 0 до e = EvenPreSums - 1

                if (e < EvenPreSums) {

                    e++;

                    cout << "0 ";

                }

                else {

                    o++;

  

                    // выводим 1, когда e = EvenPreSums

                    cout << "1 ";

                    CurrSum++;

                }

            }

            else {

                if (e < EvenPreSums) {

                    e++;

                    cout << "1 ";

                    CurrSum++;

                }

                else {

                    o++;

  

                    // выводим 0 для остальных значений

                    cout << "0 ";

                }

            }

        }

        cout << endl;

    }

}

  
// Код драйвера

int main()

{

    int N = 15;

    int even = 60, odd = 60;

    CreateArray(N, even, odd);

  

    return 0;

}

Джава

// Java реализация подхода

import java.io.*;

  

class GFG {

  

    // Функция для генерации и печати необходимого массива

    static void CreateArray(int N, int even, int odd)

    {

        int EvenPreSums = 1;

        int temp = -1;

        int OddPreSums = 0;

  

        // Находим количество нечетных сумм префиксов

        for (int i = 0; i <= N + 1; i++) {

            if (i * ((N + 1) - i) == odd) {

                temp = 0;

                OddPreSums = i;

                break;

            }

        }

  

        // Если не найдена нечетная префиксная сумма

        if (temp == -1) {

            System.out.println(temp);

        }

        else {

  

            // Расчет количества четных префиксных сумм

  

            EvenPreSums = ((N + 1) - OddPreSums);

            int e = 1;

            int o = 0;

  

            // Сохраняет текущую сумму префикса

            int CurrSum = 0;

            for (int i = 0; i < N; i++) {

  

                // Если текущая сумма префикса четна

                if (CurrSum % 2 == 0) {

  

                    // печатаем 0 до e = EvenPreSums - 1

                    if (e < EvenPreSums) {

                        e++;

                        System.out.print("0 ");

                    }

                    else {

                        o++;

  

                        // выводим 1, когда e = EvenPreSums

                        System.out.print("1 ");

                        CurrSum++;

                    }

                }

                else {

                    if (e < EvenPreSums) {

                        e++;

                        System.out.print("1 ");

                        CurrSum++;

                    }

                    else {

                        o++;

  

                        // выводим 0 для остальных значений

                        System.out.print("0 ");

                    }

                }

            }

            System.out.println();

        }

    }

  

    // Код драйвера

    public static void main(String[] args)

    {

  

        int N = 15;

        int even = 60, odd = 60;

        CreateArray(N, even, odd);

    }

}

  
// Этот код предоставлен akt_mit

python3

# Python 3 реализация подхода

  
# Функция для генерации и печати
# обязательный массив

def CreateArray(N, even, odd):

    temp = -1

      

    # Найти количество нечетных префиксных сумм

    for i in range(N + 2):

        if (i * ((N + 1) - i) == odd):

            temp = 0

            OddPreSums = i

            break

  

    # Если не найдена нечетная префиксная сумма

    if (temp == -1):

        print(temp)

    else:

          

        # Расчет числа

        Количество четных префиксных сумм

        EvenPreSums = (N + 1) - OddPreSums

        e = 1

        o = 0

  

        # Сохраняет текущую сумму префикса

        CurrSum = 0

        for i in range(N):

              

            # Если текущая сумма префикса четна

            if (CurrSum % 2 == 0):

                  

                # Печатайте 0 до e = EvenPreSums - 1

                if (e < EvenPreSums):

                    e += 1

                    print("0 ", end = "")

                else:

                    o += 1

  

                    # Печать 1, когда e = EvenPreSums

                    print("1 ", end = "")

                    CurrSum += 1

      

            else:

                if (e < EvenPreSums):

                    e += 1

                    print("1 ")

                    CurrSum += 1

                else:

                    o += 1

  

                    # Вывести 0 для остальных значений

                    print("0 ", end = "")

        print("\n", end = "")

  
# Код драйвера

if __name__ == '__main__':

    N = 15

    even = 60

    odd = 60

    CreateArray(N, even, odd)

  
# Этот код предоставлен
# Surendra_Gangwar

C #

// C # реализация подхода

using System;

  

class GFG {

  

    // Функция для генерации и печати необходимого массива

    static void CreateArray(int N, int even, int odd)

    {

        int EvenPreSums = 1;

        int temp = -1;

        int OddPreSums = 0;

  

        // Находим количество нечетных сумм префиксов

        for (int i = 0; i <= N + 1; i++) {

            if (i * ((N + 1) - i) == odd) {

                temp = 0;

                OddPreSums = i;

                break;

            }

        }

  

        // Если не найдена нечетная префиксная сумма

        if (temp == -1) {

            Console.WriteLine(temp);

        }

        else {

  

            // Расчет количества четных префиксных сумм

  

            EvenPreSums = ((N + 1) - OddPreSums);

            int e = 1;

            int o = 0;

  

            // Сохраняет текущую сумму префикса

            int CurrSum = 0;

            for (int i = 0; i < N; i++) {

  

                // Если текущая сумма префикса четна

                if (CurrSum % 2 == 0) {

  

                    // печатаем 0 до e = EvenPreSums - 1

                    if (e < EvenPreSums) {

                        e++;

                        Console.Write("0 ");

                    }

                    else {

                        o++;

  

                        // выводим 1, когда e = EvenPreSums

                        Console.Write("1 ");

                        CurrSum++;

                    }

                }

                else {

                    if (e < EvenPreSums) {

                        e++;

                        Console.Write("1 ");

                        CurrSum++;

                    }

                    else {

                        o++;

  

                        // выводим 0 для остальных значений

                        Console.Write("0 ");

                    }

                }

            }

            Console.WriteLine();

        }

    }

  

    // Код драйвера

    static public void Main()

    {

        int N = 15;

        int even = 60, odd = 60;

        CreateArray(N, even, odd);

    }

}

  
// Этот код предоставлен Tushil

PHP

<?php
// PHP реализация подхода

  
// Функция для генерации и печати необходимого массива

function CreateArray($N, $even, $odd

    $temp = -1; 

    $OddPreSums = 0; 

  

    // Находим количество нечетных сумм префиксов

    for ($i = 0; $i <= $N + 1; $i++) 

    

        if ($i * (($N + 1) - $i) == $odd

        

            $temp = 0; 

            $OddPreSums = $i

            break

        

    

  

    // Если не найдена нечетная префиксная сумма

    if ($temp == -1) 

    

        echo temp ; 

    

    else

    

  

        // Расчет количества четных префиксных сумм

        $EvenPreSums = ($N + 1) - $OddPreSums

        $e = 1; 

        $o = 0; 

  

        // Сохраняет текущую сумму префикса

        $CurrSum = 0; 

        for ($i = 0; $i < $N; $i++)

        

  

            // Если текущая сумма префикса четна

            if ($CurrSum % 2 == 0)

            

  

                // печатаем 0 до e = EvenPreSums - 1

                if ($e < $EvenPreSums

                

                    $e++; 

                    echo "0 "

                

                else

                

                    $o++; 

  

                    // выводим 1, когда e = EvenPreSums

                    echo "1 "

                    $CurrSum++; 

                

            

            else 

            

                if ($e < $EvenPreSums)

                

                    $e++; 

                    echo "1 "

                    $CurrSum++; 

                

                else

                

                    $o++; 

  

                    // выводим 0 для остальных значений

                    echo "0 "

                

            

        

        echo "\n"

    

  
// Код драйвера

$N = 15; 

$even = 60;

$odd = 60; 

CreateArray($N, $even, $odd); 

  
// Этот код предоставлен AnkitRai01
?>

Выход:

0 0 0 0 0 0 0 0 0 1 0 0 0 0 0

Рекомендуемые посты:

Создайте массив, в котором подсчет четных и нечетных подмассивов равен E и O соответственно

0.00 (0%) 0 votes