Count all Pairs in an Array with Balanced Digit Sums and Even-Digit Concatenation - Coding

Given an array of integers arr[], A pairs (i, j) is valid, which follows the below two conditions:

Concatenation of integer at i’th and j’th index have even number of digits (Even digit Concatenation)
Sum of digits in the first half = sum of digits in the second half (Balanced Digit Sum)

The task is to count all such valid pairs in the given array with Balanced Digit Sums and Even-Digit Concatenation.

Example:

Input: arr = {1,1,1}
Output: 9

Input: arr[] = {“2”, “22”, “222”, “2222”, “22222”}
Output: 13

Approach:

The intuition behind the solution lies in the observation that a valid pair must satisfy two conditions:

Concatenation has even number of digits: This implies that the length of the string formed by concatenating the two strings must be even.

Sum of digits in first half = Sum of digits in second half: This means that the sum of digits in the first half of the concatenated string must be equal to the sum of digits in the second half.

Steps-by-step approach:

Create an array sum to store the cumulative sum of digits.
Create a 2D array str to store the strings.
Initialize a map mp to store the number of occurrences of each pair of values.
Calculate Cumulative Sum and Populate Map
- Loop through each element (i):
  - Get the string from the strings array.
  - Loop through each character in the string and calculate the sum of its digits.
  - Loop through each character in the string and calculate the cumulative sum of digits.
  - For each character in the string, create a unique key based on the sum and position. Update the count for this key in the map.
Count Valid Pairs
- Initialize ans as 0.
- Loop through each element (i) again:
  - Get the string from the strings array.
  - For each character in the string, check for valid pairs using the sum and length. Update the answer with the count from the map.
Print the final result, which represents the total number of valid pairs.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
// Maximum number of elements
const int N = 200010;
 
// Store cumulative sum of digits
ll sum[N];
 
// Array to store strings
char str[N][10];
 
// Function to solve the problem
ll solve(int n,string strings[])
{
    // Map to store number of occurrences of each pair of
    // values
    map<pair<ll, ll>, int> mp;
 
    // Loop through each element
    for (ll i = 1; i <= n; ++i) {
        // Get the string
        string str_i = strings[i - 1];
        ll len = str_i.length();
 
        // Calculate the sum of all digits
        ll ssum = 0;
        for (ll j = 0; j < len; ++j) {
            ssum += str_i[j] - '0';
        }
 
        // Calculate the cumulative sum of digits
        for (ll j = 0; j < len; ++j) {
            sum[i] += str_i[j] - '0';
 
            // Create a unique key based on sum and position
            pair<ll, ll> key
                = { 2 * sum[i] - ssum, 2 * (j + 1) - len };
 
            // Increase the count for this key
            mp[key]++;
        }
    }
 
    // Total number of valid pairs
    ll ans = 0;
 
    // Loop through each element again
    for (ll i = 1; i <= n; ++i) {
        // Get the string
        string str_i = strings[i - 1];
        ll len = str_i.length();
 
        // Check for valid pairs with the current sum and
        // length
        ans += mp[{ sum[i], len }] + mp[{ -sum[i], -len }];
    }
 
    return ans;
}
 
// Driver code
int main()
{
    // Define static input
    ll n = 5;
    string strings[]
        = { "2", "22", "222", "2222", "22222" };
 
    // Solve the problem and print the result
    cout << solve(n,strings) << endl;
 
    return 0;
}

Java

import java.util.AbstractMap;
import java.util.HashMap;
import java.util.Map;
 
public class Main {
    // Maximum number of elements
    private static final int N = 200010;
 
    // Store cumulative sum of digits
    private static long[] sum = new long[N];
 
    // Function to solve the problem
    private static long solve(int n, String[] strings)
    {
        // Map to store the number of occurrences of each
        // pair of values
        Map<AbstractMap.SimpleEntry<Long, Long>, Integer> mp
            = new HashMap<>();
 
        // Loop through each element
        for (long i = 1; i <= n; ++i) {
            // Get the string
            String str_i = strings[(int)(i - 1)];
            int len = str_i.length();
 
            // Calculate the sum of all digits
            long ssum = 0;
            for (int j = 0; j < len; ++j) {
                ssum += str_i.charAt(j) - '0';
            }
 
            // Calculate the cumulative sum of digits
            for (int j = 0; j < len; ++j) {
                sum[(int)i] += str_i.charAt(j) - '0';
 
                // Create a unique key based on sum and
                // position
                AbstractMap.SimpleEntry<Long, Long> key
                    = new AbstractMap.SimpleEntry<>(
                        2 * sum[(int)i] - ssum,
                        2 * (j + 1L) - len);
 
                // Increase the count for this key
                mp.put(key, mp.getOrDefault(key, 0) + 1);
            }
        }
 
        // Total number of valid pairs
        long ans = 0;
 
        // Loop through each element again
        for (long i = 1; i <= n; ++i) {
            // Get the string
            String str_i = strings[(int)(i - 1)];
            int len = str_i.length();
 
            // Check for valid pairs with the current sum
            // and length
            ans += mp.getOrDefault(
                       new AbstractMap.SimpleEntry<>(
                           sum[(int)i], (long)len),
                       0)
                   + mp.getOrDefault(
                       new AbstractMap.SimpleEntry<>(
                           -sum[(int)i], (long)-len),
                       0);
        }
 
        return ans;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        // Define static input
        int n = 5;
        String[] strings
            = { "2", "22", "222", "2222", "22222" };
 
        // Solve the problem and print the result
        System.out.println(solve(n, strings));
    }
}

Python3

# Python program for the above approach
# Maximum number of elements
N = 200010
 
# Store cumulative sum of digits
sums = [0] * N
 
# Function to solve the problem
def solve(n, strings):
    # Map to store number of occurrences of each pair of values
    mp = {}
 
    # Loop through each element
    for i in range(1, n + 1):
        # Get the string
        str_i = strings[i - 1]
        length = len(str_i)
 
        # Calculate the sum of all digits
        ssum = sum(int(digit) for digit in str_i)
 
        # Calculate the cumulative sum of digits
        for j in range(length):
            sums[i] += int(str_i[j])
 
            # Create a unique key based on sum and position
            key = (2 * sums[i] - ssum, 2 * (j + 1) - length)
 
            # Increase the count for this key
            mp[key] = mp.get(key, 0) + 1
 
    # Total number of valid pairs
    ans = 0
 
    # Loop through each element again
    for i in range(1, n + 1):
        # Get the string
        str_i = strings[i - 1]
        length = len(str_i)
 
        # Check for valid pairs with the current sum and length
        ans += mp.get((sums[i], length), 0) + mp.get((-sums[i], -length), 0)
 
    return ans
 
# Driver code
if __name__ == "__main__":
    # Define static input
    n = 5
    strings = ["2", "22", "222", "2222", "22222"]
 
    # Solve the problem and print the result
    print(solve(n, strings))
 
# This code is contributed by Susobhan Akhuli

C#

using System;
using System.Collections.Generic;
 
class Program
{
    // Maximum number of elements
    const int N = 200010;
 
    // Store cumulative sum of digits
    static long[] sum = new long[N];
 
    // Function to solve the problem
    static long Solve(int n, string[] strings)
    {
        // Map to store number of occurrences of each pair of values
        Dictionary<long, int> positiveKeys = new Dictionary<long, int>();
        Dictionary<long, int> negativeKeys = new Dictionary<long, int>();
 
        // Loop through each element
        for (long i = 1; i <= n; ++i)
        {
            // Get the string
            string str_i = strings[i - 1];
            long len = str_i.Length;
 
            // Calculate the sum of all digits
            long ssum = 0;
            for (long j = 0; j < len; ++j)
            {
                ssum += str_i[(int)j] - '0';
            }
 
            // Calculate the cumulative sum of digits
            for (long j = 0; j < len; ++j)
            {
                sum[i] += str_i[(int)j] - '0';
 
                // Create unique keys based on sum and position
                long positiveKey = 2 * sum[i] - ssum;
                long negativeKey = 2 * (j + 1) - len;
 
                // Increase the count for these keys
                if (positiveKeys.ContainsKey(positiveKey))
                    positiveKeys[positiveKey]++;
                else
                    positiveKeys[positiveKey] = 1;
 
                if (negativeKeys.ContainsKey(negativeKey))
                    negativeKeys[negativeKey]++;
                else
                    negativeKeys[negativeKey] = 1;
            }
        }
 
        // Total number of valid pairs
        long ans = 0;
 
        // Loop through each element again
        for (long i = 1; i <= n; ++i)
        {
            // Get the string
            string str_i = strings[i - 1];
            long len = str_i.Length;
 
            // Check for valid pairs with the current sum and length
            long positiveKey = sum[i];
            long negativeKey = -len;
 
            if (positiveKeys.ContainsKey(positiveKey))
                ans += positiveKeys[positiveKey];
 
            if (negativeKeys.ContainsKey(negativeKey))
                ans += negativeKeys[negativeKey];
        }
 
        return ans;
    }
 
    // Driver code
    static void Main()
    {
        // Define static input
        long n = 5;
        string[] strings = { "2", "22", "222", "2222", "22222" };
 
        // Solve the problem and print the result
        Console.WriteLine(Solve((int)n, strings));
    }
}

Javascript

// Javascript program for the above approach
 
// Store cumulative sum of digits
let sum = new Array(200010).fill(0);
 
// Function to solve the problem
function solve(n, strings) {
    // Map to store number of occurrences of each pair of values
    let mp = new Map();
 
    // Loop through each element
    for (let i = 1; i <= n; ++i) {
        // Get the string
        let str_i = strings[i - 1];
        let len = str_i.length;
 
        // Calculate the sum of all digits
        let ssum = 0;
        for (let j = 0; j < len; ++j) {
            ssum += parseInt(str_i[j]);
        }
 
        // Calculate the cumulative sum of digits
        for (let j = 0; j < len; ++j) {
            sum[i] += parseInt(str_i[j]);
 
            // Create a unique key based on sum and position
            let key = `${2 * sum[i] - ssum},${2 * (j + 1) - len}`;
 
            // Increase the count for this key
            if (mp.has(key)) {
                mp.set(key, mp.get(key) + 1);
            } else {
                mp.set(key, 1);
            }
        }
    }
 
    // Total number of valid pairs
    let ans = 0;
 
    // Loop through each element again
    for (let i = 1; i <= n; ++i) {
        // Get the string
        let str_i = strings[i - 1];
        let len = str_i.length;
 
        // Check for valid pairs with the current sum and length
        ans += (mp.get(`${sum[i]},${len}`) || 0) + (mp.get(`${-sum[i]},${-len}`) || 0);
    }
 
    return ans;
}
 
// Define static input
let n = 5;
let strings = ["2", "22", "222", "2222", "22222"];
 
// Solve the problem and print the result
console.log(solve(n, strings)); // Output: 13
 
// This code is contributed by Susobhan Akhuli

Output

Time Complexity: O(n*m*log(n*m)), where n is the number of elements (strings) in the array and m is the maximum length of any string.
Auxiliary Space: O(n*m)

Reffered: https://www.geeksforgeeks.org

Competitive Programming

Related
Find the minimum number containing only 0s and 1s that represents N.
Hashing in Competitive Programming
Find the path from root to a vertex such that all K vertices belongs to this path or 1 distance away
Find Edge Weights in a Spanning Tree with Edge (u, v)
Find the Longest Non-Prefix-Suffix Substring in the Given String

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	14