Найдите общее количество подмассивов из 0

Дан массив arr[] длины N, состоящий из 0 и 1, задача состоит в том, чтобы найти общее количество подмассивов из 0.

Примеры:

Ввод: N = 4, arr[] = {0, 0, 1, 0}
Вывод: 4
Объяснение: Ниже приведены подмассивы длины 1: {0}, {0}, {0} — 3 длины 2: {0, 0} — 1. Всего подмассивов: 3 + 1 = 4

Ввод: N = 4, arr[] = {0, 0, 0, 0}
Вывод: 10
Объяснение: Ниже приведены подмассивы

• длина 1: {0}, {0}, {0}, {0} = 4
• длина 2: {0, 0}, {0, 0}, {0, 0} = 3
• длина 3: {0, 0, 0}, {0, 0, 0} = 2
• длина 4: {0, 0, 0, 0} = 1

Всего подмассивов: 4 + 3 + 2 + 1 = 10

Подход: Чтобы решить проблему, следуйте следующей идее:

Идея состоит в том, что если есть n последовательных нулей, то всего ( (n+1) * (n))/2 0 подмассивов.

Этапы реализации кода:

• Сохраните переменную для ответа, инициализируйте ее 0 и еще одну переменную для счетчика, который отслеживает количество непрерывных нулей.
• Запустите цикл for и пройдитесь по массиву.
  • Подсчитайте количество смежных нулей.
  • Включение count*(count+1)/2 в решение, потому что count*(count+1)/2 подмассивы могут быть созданы с использованием count количества непрерывных нулей.
• Добавьте count*(count+1)/2к ответу, если количество больше нуля.
• Вернуть ответ.

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

Java

// Java Implementation of approach

import java.util.*;

 

public class GFG {

 

    // Function to count the

    // number of subarrays

    static long no_of_subarrays(int N, int[] arr)

    {

        long count = 0, answer = 0;

 

        // Loop through the array

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

 

            // If the element is 0,

            // increment the count

            if (arr[i] == 0) {

                count++;

            }

 

            // If the element is not 0,

            // calculate the number of

            // subarrays that can be formed

            // with the previous 0's

            else {

                answer += ((count * (count + 1)) / 2);

                count = 0;

            }

        }

 

        // Calculate the number of

        // subarrays that can be formed

        // with any remaining 0's

        answer += ((count * (count + 1)) / 2);

        return answer;

    }

 

    // Driver code

    public static void main(String[] args)

    {

        int[] arr = { 0, 0, 1, 0 };

        int N = arr.length;

 

        // Function call

        long result = no_of_subarrays(N, arr);

        System.out.println(result);

    }

}

Выход

4

Временная сложность: O(N).
Вспомогательное пространство: O(1).