Dada una array arr[] de tamaño N y un entero K ., la tarea es contar el número de subarreglos con suma única con suma como máximo K.
Ejemplos :
Entrada : N = 3, arr[] = {1, 0, 1}, K = 1
Salida : 3
Explicación : Todos los subarreglos son [1], [0], [1], [1, 0], [0, 1], [1, 0, 1] & La suma de estos subarreglos son {1, 0, 1, 1, 1, 2} respectivamente. Solo hay 2 sumas posibles distintas menores o iguales a 1
Entrada : N = 1, arr[] = {1}, K = 0
Salida : 0
Enfoque : La tarea se puede resolver calculando sumas de cada subarreglo y almacenándolos en un HashMap . Iterar sobre HashMap e incrementar el conteo, si la suma es como máximo K
A continuación se muestra la implementación del enfoque anterior.
C++14
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to calculate the valid sums void solve(int arr[], int n, int k) { // Store the distinct subarray sums unordered_map<int, int> occ; int cur = 0; for (int i = 0; i < n; i++) { cur = 0; for (int j = i; j < n; j++) { cur += arr[j]; occ[cur]++; } } // Stores the answer int ans = 0; for (auto x : occ) { if (x.first <= k) ans++; } cout << ans << endl; } // Driver Code int main() { int N = 3, K = 1; int arr[3] = { 1, 0, 1 }; solve(arr, N, K); return 0; }
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to calculate the valid sums static void solve(int arr[], int n, int k) { // Store the distinct subarray sums HashMap<Integer,Integer> occ = new HashMap<Integer,Integer>(); int cur = 0; for (int i = 0; i < n; i++) { cur = 0; for (int j = i; j < n; j++) { cur += arr[j]; if(occ.containsKey(cur)){ occ.put(cur, occ.get(cur)+1); } else{ occ.put(cur, 1); } } } // Stores the answer int ans = 0; for (Map.Entry<Integer,Integer> x : occ.entrySet()) { if (x.getKey() <= k) ans++; } System.out.print(ans +"\n"); } // Driver Code public static void main(String[] args) { int N = 3, K = 1; int arr[] = { 1, 0, 1 }; solve(arr, N, K); } } // This code is contributed by 29AjayKumar
Python3
# python program for the above approach # Function to calculate the valid sums def solve(arr, n, k): # Store the distinct subarray sums occ = {} cur = 0 for i in range(0, n): cur = 0 for j in range(i, n): cur += arr[j] if cur in occ: occ[cur] += 1 else: occ[cur] = 1 # Stores the answer ans = 0 for x in occ: if (x <= k): ans += 1 print(ans) # Driver Code if __name__ == "__main__": N = 3 K = 1 arr = [1, 0, 1] solve(arr, N, K) # This code is contributed by rakeshsahni
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG { // Function to calculate the valid sums static void solve(int[] arr, int n, int k) { // Store the distinct subarray sums Dictionary<int, int> occ = new Dictionary<int, int>(); int cur = 0; for (int i = 0; i < n; i++) { cur = 0; for (int j = i; j < n; j++) { cur += arr[j]; if (!occ.ContainsKey(cur)) occ[cur] = 0; else occ[cur]++; } } // Stores the answer int ans = 0; foreach(KeyValuePair<int, int> x in occ) { if (x.Key <= k) ans++; } Console.WriteLine(ans); } // Driver Code public static void Main() { int N = 3, K = 1; int[] arr = { 1, 0, 1 }; solve(arr, N, K); } } // This code is contributed by ukasp.
Javascript
<script> // JavaScript code for the above approach // Function to calculate the valid sums function solve(arr, n, k) { // Store the distinct subarray sums let occ = new Map(); let cur = 0; for(let i = 0; i < n; i++) { cur = 0; for(let j = i; j < n; j++) { cur += arr[j]; if (occ.has(cur)) { occ.set(cur, occ.get(cur) + 1) } else { occ.set(cur, 1); } } } // Stores the answer let ans = 0; for(let[key, value] of occ) { if (key <= k) ans++; } document.write(ans + '<br>'); } // Driver Code let N = 3, K = 1; let arr = [ 1, 0, 1 ]; solve(arr, N, K); // This code is contributed by Potta Lokesh </script>
2
Complejidad de Tiempo : O(N 2 )
Espacio Auxiliar : O(N)