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