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

Веб-разработка на Java Программирование и разработка

Дан массив 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).

Читайте также:  Свойство переполнения CSS
Оцените статью
bestprogrammer.ru
Добавить комментарий