Dada una array arr[] de longitud N y un número entero X , la tarea es contar ningún subarreglo que tenga una suma de dígitos igual a X.
Ejemplos:
Entrada: arr[] = {10, 5, 13, 20, 9}, X = 6
Salida: 2
Explicación: Hay dos subarreglos que tienen una suma de dígitos igual a 6.
{10, 5} => (1 + 0 ) + 5 = 6 y {13 , 20} => (1 + 3) + (2 + 0) = 6.Entrada: arr[] = {50, 30, 13, 21, 10}, X = 8
Salida: 2
Explicación: Hay dos subarreglos que tienen una suma de dígitos igual a 8.
{50, 30} => (5+0 ) + (3+0) = 8 y {13, 21, 10} => (1+3) + (2+1) + (1+0) = 8.
Enfoque ingenuo: el enfoque ingenuo del problema se basa en verificar cada subarreglo. Para cada subarreglo, verifique si tiene una suma de dígitos igual a X o no y aumente el conteo en consecuencia.
Complejidad de tiempo: O(N 2 * d) donde d es el número máximo de dígitos en un elemento de array
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque eficiente sería mediante el uso de un mapa . Utilice el mapa para realizar un seguimiento de las sumas de dígitos ya obtenidas. Realice un seguimiento de la suma de dígitos actual y, si es igual a X , cuente el incremento. Y también verifique en el mapa para (suma actual – X) . Siga actualizando la suma de dígitos actual en el mapa.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to implement the approach #include <bits/stdc++.h> using namespace std; // Function to replace the array elements // with their digit sum value void convertInteger(int arr[], int N) { int i, sum = 0; for (i = 0; i < N; i++) { int temp = arr[i]; while (temp) { // Store the last digit int l = temp % 10; sum += l; temp = temp / 10; } // Update the integer by // its digit sum arr[i] = sum; sum = 0; } } // Function to count number of subarrays // having digit sum equal to X. int CountSubarraySum(int arr[], int N, int X) { // replace all the array element into // their digit sum value convertInteger(arr, N); // Map to store the digit sum unordered_map<int, int> mp; int count = 0; // Sum of elements so far. int sum = 0; // Loop to calculate number of subarrays for (int i = 0; i < N; i++) { // Add current array element // to the digit sum so far. sum += arr[i]; // Increment count if current sum // equal to X if (sum == X) count++; // Find (sum - X) in the map if (mp.find(sum - X) != mp.end()) count += (mp[sum - X]); // Update the map with sum for // count of different values of X mp[sum]++; } return count; } // Driver code int main() { int arr[] = { 50, 30, 13, 21, 10 }; int sum = 8; int N = sizeof(arr) / sizeof(arr[0]); cout << CountSubarraySum(arr, N, sum); return 0; }
Java
// Java program to implement the approach import java.util.*; class GFG { // Function to replace the array elements // with their digit sum value public static void convertInteger(int arr[], int N) { int i, sum = 0; for (i = 0; i < N; i++) { int temp = arr[i]; while (temp > 0) { // Store the last digit int l = temp % 10; sum += l; temp = temp / 10; } // Update the integer by // its digit sum arr[i] = sum; sum = 0; } } // Function to count number of subarrays // having digit sum equal to X. public static int CountSubarraySum(int arr[], int N, int X) { // replace all the array element into // their digit sum value convertInteger(arr, N); // Map to store the digit sum HashMap<Integer, Integer> mp = new HashMap<>(); int count = 0; // Sum of elements so far. int sum = 0; // Loop to calculate number of subarrays for (int i = 0; i < N; i++) { // Add current array element // to the digit sum so far. sum += arr[i]; // Increment count if current sum // equal to X if (sum == X) count++; // Find (sum - X) in the map if (mp.containsKey(sum - X)) count += (mp.get(sum - X)); // Update the map with sum for // count of different values of X if (mp.containsKey(sum)) mp.put(sum, mp.get(sum) + 1); else mp.put(sum, 1); } return count; } // driver code public static void main(String[] args) { int arr[] = { 50, 30, 13, 21, 10 }; int sum = 8; int N = arr.length; System.out.println(CountSubarraySum(arr, N, sum)); } } // This code is contributed by Palak Gupta
Python3
# Python code for the above approach # Function to replace the array elements # with their digit sum value def convertInteger(arr, N): sum = 0 for i in range(N): temp = arr[i] while (temp): # Store the last digit l = temp % 10 sum += l temp = (temp // 10) # Update the integer by # its digit sum arr[i] = sum sum = 0 # Function to count number of subarrays # having digit sum equal to X. def CountSubarraySum(arr, N, X): # replace all the array element into # their digit sum value convertInteger(arr, N) # Map to store the digit sum mp = {} count = 0 # Sum of elements so far. sum = 0 # Loop to calculate number of subarrays for i in range(N): # Add current array element # to the digit sum so far. sum += arr[i] # Increment count if current sum # equal to X if (sum == X): count += 1 # Find (sum - X) in the map if ((sum - X) in mp): count += (mp[(sum - X)]) # Update the map with sum for # count of different values of X if (sum in mp): mp[sum] += 1 else: mp[sum] = 1 return count # Driver code arr = [50, 30, 13, 21, 10] sum = 8 N = len(arr) print(CountSubarraySum(arr, N, sum)) # This code is contributed by gfgking
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG { // Function to replace the array elements // with their digit sum value static void convertInteger(int[] arr, int N) { int i, sum = 0; for (i = 0; i < N; i++) { int temp = arr[i]; while (temp != 0) { // Store the last digit int l = temp % 10; sum += l; temp = temp / 10; } // Update the integer by // its digit sum arr[i] = sum; sum = 0; } } // Function to count number of subarrays // having digit sum equal to X. static int CountSubarraySum(int[] arr, int N, int X) { // replace all the array element into // their digit sum value convertInteger(arr, N); // Map to store the digit sum Dictionary<int, int> mp = new Dictionary<int, int>(); int count = 0; // Sum of elements so far. int sum = 0; // Loop to calculate number of subarrays for (int i = 0; i < N; i++) { // Add current array element // to the digit sum so far. sum += arr[i]; // Increment count if current sum // equal to X if (sum == X) count++; // Find (sum - X) in the map if (mp.ContainsKey(sum - X)) count += (mp[sum - X]); // Update the map with sum for // count of different values of X if(mp.ContainsKey(sum)) { mp[sum] = i; } else{ mp.Add(sum, i); } } return count; } // Driver Code public static void Main() { int[] arr = { 50, 30, 13, 21, 10 }; int sum = 8; int N = arr.Length; Console.Write(CountSubarraySum(arr, N, sum)); } } // This code is contributed by sanjoy_62.
Javascript
<script> // JavaScript code for the above approach // Function to replace the array elements // with their digit sum value function convertInteger(arr, N) { let i, sum = 0; for (i = 0; i < N; i++) { let temp = arr[i]; while (temp) { // Store the last digit let l = temp % 10; sum += l; temp = Math.floor(temp / 10); } // Update the integer by // its digit sum arr[i] = sum; sum = 0; } } // Function to count number of subarrays // having digit sum equal to X. function CountSubarraySum(arr, N, X) { // replace all the array element into // their digit sum value convertInteger(arr, N); // Map to store the digit sum let mp = new Map(); let count = 0; // Sum of elements so far. let sum = 0; // Loop to calculate number of subarrays for (let i = 0; i < N; i++) { // Add current array element // to the digit sum so far. sum += arr[i]; // Increment count if current sum // equal to X if (sum == X) count++; // Find (sum - X) in the map if (mp.has(sum - X)) count += (mp.get(sum - X)); // Update the map with sum for // count of different values of X if (mp.has(sum)) { mp.set(sum, mp.get(sum) + 1) } else { mp.set(sum, 1); } } return count; } // Driver code let arr = [50, 30, 13, 21, 10]; let sum = 8; let N = arr.length; document.write(CountSubarraySum(arr, N, sum)); // This code is contributed by Potta Lokesh </script>
2
Complejidad de tiempo: O(N * d) donde d es el número máximo de dígitos en un elemento de array
Espacio auxiliar: O(N)