Given a numeric string str, the task is to calculate the number of substrings with the sum of digits equal to their length.
Examples:
Input: str = “112112”
Output: 6
Explanation:
Substrings “1”, “1”, “11”, “1”, “1”, “11” satisfy the given condition.Input: str = “1101112”
Output: 12
Naive Approach: The simplest solution is to generate all substrings of the given string and for each substring, check if its sum is equal to its length or not. For each substring found to be true, increase count.
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to count the number of// substrings with sum equal to lengthint countSubstrings(string s, int n){ int count = 0; for (int i = 0; i < n; i++) { int sum = 0; for (int j = i; j < n; j++) { sum += s[j] - '0'; if (j - i + 1 == sum) { count++; } } } // Return count return count;}// Driver Codeint main(){ string str = "1101112"; int n = str.length(); cout << countSubstrings(str, n) << endl; return 0;} |
Java
// Java program to implement// the above approachimport java.util.*;class GFG { // Function to count the number of // substrings with sum equal to length static int countSubStrings(String s, int n) { int count = 0; for (int i = 0; i < n; i++) { int sum = 0; for (int j = i; j < n; j++) { sum += s.charAt(j) - '0'; if (j - i + 1 == sum) { count++; } } } // Return count return count; } // Driver Code public static void main(String[] args) { String str = "1101112"; int n = str.length(); System.out.print(countSubStrings(str, n) + "\n"); }} |
Python3
def countSubstrings(s: str, n: int): count = 0 for i in range(n): sum = 0 for j in range(i, n): sum += int(s[j]) if (j - i + 1 == sum): count += 1 return countstr = "1101112"n = len(str)print(countSubstrings(str, n)) |
C#
using System;public class Program { // Function to count the number of // substrings with sum equal to length static int CountSubStrings(string s, int n) { int count = 0; for (int i = 0; i < n; i++) { int sum = 0; for (int j = i; j < n; j++) { sum += s[j] - '0'; if (j - i + 1 == sum) { count++; } } } // Return count return count; } static void Main(string[] args) { string str = "1101112"; int n = str.Length; Console.WriteLine(CountSubStrings(str, n)); }} |
Javascript
// Javascript Program to implement// the above approach// Function to count the number of// substrings with sum equal to lengthfunction countSubstrings( s, n){ let count = 0; for (let i = 0; i < n; i++) { let sum = 0; for (let j = i; j < n; j++) { sum += s[j] - '0'; if (j - i + 1 == sum) { count++; } } } // Return count return count;}// Driver Codelet str = "1101112";let n = str.length;console.log(countSubstrings(str, n)); // This code is contributed by agrawalpoojaa976. |
Output
12
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: We can see that we want the sum of any substring of the string to be equal to its length. Let’s say we already have a prefix array pref calculated such that pref[i] denotes the sum of all the elements from index 0 to index i. Now, we can visualise the question in terms of below given equations:
pref[r] – pref[l-1] = r – l + 1
// taking similar terms together
pref[r] – r = pref[l-1] – l + 1
pref[r] – r = pref[l-1] – (l – 1)
// say i = l – 1
pref[r] – r = pref[i] – i
Now for each index i we just need to check how many times the value of pref[i] – i occured previously. This can be easily solved using a Hashmap and maintaining a sum variable which gives the sum of all elements till index i.
Below is the implementation of the above approach:
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to count the number of// substrings with sum equal to lengthint countSubstrings(string s, int n){ int count = 0, sum = 0; // Stores the count of substrings unordered_map<int, int> mp; mp[0]++; for (int i = 0; i < n; ++i) { // Add character to sum sum += (s[i] - '0'); // Add count of substrings to result count += mp[sum - (i + 1)]; // Increase count of subarrays ++mp[sum - (i + 1)]; } // Return count return count;}// Driver Codeint main(){ string str = "112112"; int n = str.length(); cout << countSubstrings(str, n) << endl; return 0;} |
Java
// Java program to implement// the above approachimport java.util.*;class GFG{// Function to count the number of// subStrings with sum equal to lengthstatic int countSubStrings(String s, int n){ int count = 0, sum = 0; // Stores the count of subStrings HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>(); mp.put(0, 1); for(int i = 0; i < n; ++i) { // Add character to sum sum += (s.charAt(i)- '0'); // Add count of subStrings to result count += mp.containsKey(sum - (i + 1)) == true ? mp.get(sum - (i + 1)) : 0; // Increase count of subarrays if(!mp.containsKey(sum - (i + 1))) mp.put(sum - (i + 1), 1); else mp.put(sum - (i + 1), mp.get(sum - (i + 1)) + 1); } // Return count return count;}// Driver Codepublic static void main(String[] args){ String str = "112112"; int n = str.length(); System.out.print(countSubStrings(str, n) + "\n");}}// This code is contributed by Amit Katiyar |
Python3
# Python3 program to implement # the above approachfrom collections import defaultdict# Function to count the number of # substrings with sum equal to lengthdef countSubstrings(s, n): count, sum = 0, 0 # Stores the count of substrings mp = defaultdict(lambda : 0) mp[0] += 1 for i in range(n): # Add character to sum sum += ord(s[i]) - ord('0') # Add count of substrings to result count += mp[sum - (i + 1)] # Increase count of subarrays mp[sum - (i + 1)] += 1 # Return count return count# Driver codestr = '112112'n = len(str)print(countSubstrings(str, n))# This code is contributed by Stuti Pathak |
C#
// C# program to implement// the above approachusing System;using System.Collections.Generic;class GFG{// Function to count the number of// subStrings with sum equal to lengthstatic int countSubStrings(String s, int n){ int count = 0, sum = 0; // Stores the count of subStrings Dictionary<int, int> mp = new Dictionary<int, int>(); mp.Add(0, 1); for(int i = 0; i < n; ++i) { // Add character to sum sum += (s[i]- '0'); // Add count of subStrings to result count += mp.ContainsKey(sum - (i + 1)) == true ? mp[sum - (i + 1)] : 0; // Increase count of subarrays if(!mp.ContainsKey(sum - (i + 1))) mp.Add(sum - (i + 1), 1); else mp[sum - (i + 1)] = mp[sum - (i + 1)] + 1; } // Return count return count;}// Driver Codepublic static void Main(String[] args){ String str = "112112"; int n = str.Length; Console.Write(countSubStrings(str, n) + "\n");}}// This code is contributed by Rohit_ranjan |
Javascript
<script>// Javascript Program to implement// the above approach// Function to count the number of// substrings with sum equal to lengthfunction countSubstrings(s, n){ var count = 0, sum = 0; // Stores the count of substrings var mp = new Map(); if(mp.has(0)) mp.set(0, mp.get(0)+1) else mp.set(0, 1); for (var i = 0; i < n; ++i) { // Add character to sum sum += (s[i].charCodeAt(0) - '0'.charCodeAt(0)); // Add count of substrings to result if(mp.has(sum - (i + 1))) count += mp.get(sum - (i + 1)); // Increase count of subarrays if(mp.has(sum - (i + 1))) mp.set(sum - (i + 1), mp.get(sum - (i + 1))+1) else mp.set(sum - (i + 1), 1) } // Return count return count;}// Driver Codevar str = "112112";var n = str.length;document.write( countSubstrings(str, n));</script> |
Output
6
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
