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>
Producción
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)