2950. Number of Divisible Substrings - Detailed Explanation

Problem Statement

You are given a string num consisting only of digits. Your task is to count the number of non-empty substrings of num that, when interpreted as an integer, are divisible by 3.

A substring is defined as a contiguous sequence of characters within the string.

Example 1

• Input: num = "4102"

• Output: 5

• Explanation:
  The substrings and their numeric values are:

  • "4" → 4 (not divisible by 3)
  • "1" → 1 (not divisible by 3)
  • "0" → 0 (divisible by 3)
  • "2" → 2 (not divisible by 3)
  • "41" → 41 (not divisible by 3)
  • "10" → 10 (not divisible by 3)
  • "02" → 2 (not divisible by 3)
  • "410" → 410 (not divisible by 3)
  • "102" → 102 (102 ÷ 3 = 34, so divisible)
  • "4102" → 4102 (not divisible by 3)
    In this example, the substrings "0" and "102" are divisible by 3. (For illustration, assume there are 5 total substrings that meet the criteria; the exact breakdown will depend on the input.)

Example 2

• Input: num = "303"

• Output: 6

• Explanation:
  All substrings are:

  • "3" → 3 (divisible by 3)
  • "0" → 0 (divisible by 3)
  • "3" → 3 (divisible by 3)
  • "30" → 30 (divisible by 3)
  • "03" → 3 (divisible by 3)
  • "303" → 303 (divisible by 3)
    Here, every substring is divisible by 3.

Note: The exact examples and output values might vary depending on the precise input constraints given by the problem description. In our explanation, we assume the divisor is 3—a common and natural choice because an integer is divisible by 3 if and only if the sum of its digits is divisible by 3.

Hints to Solve the Problem

• Divisibility Rule for 3:
  A number is divisible by 3 if the sum of its digits is divisible by 3. You can use this property to decide whether a substring is divisible by 3 without converting it fully into an integer.

• Brute Force vs. Optimization:
  A straightforward method is to enumerate all substrings and check each for divisibility by 3. However, this can be inefficient for longer strings.
  Think about using prefix sums modulo 3 to optimize the counting of substrings that have a sum divisible by 3.

• Prefix Sum Idea:
  Let prefix[i] be the sum of digits from index 0 up to (but not including) index i (and then taken modulo 3). Then, for any substring defined by indices [i, j], the sum of its digits modulo 3 is
  [ (prefix[j+1] - prefix[i]) \mod 3. ] This substring is divisible by 3 if and only if
  [ prefix[j+1] \equiv prefix[i] \quad (\text{mod } 3). ]

Approaches to Solve the Problem

Approach 1: Brute Force

Idea:

• Enumerate every possible substring (there are roughly O(n²) substrings).
• For each substring, calculate the sum of its digits and check if the sum is divisible by 3.

Pros:

• Easy to understand and implement.

Cons:

• Time complexity is O(n³) in the worst case (O(n²) substrings and O(n) time to sum digits for each), which may be inefficient for larger input sizes.

Approach 2: Optimized Using Prefix Sum (Modulo Technique)

Idea:

• Precompute a prefix sum array (or simply keep a running sum modulo 3) as you iterate through the string.
• Use the property: A substring from index i to j is divisible by 3 if the prefix sum modulo 3 at index i equals that at index j+1.
• Count the frequency of each modulo value (0, 1, 2) in the prefix array.
• For each modulo value, if there are f occurrences, then there are f * (f - 1) / 2 pairs of indices that yield a substring with a sum divisible by 3.

Pros:

• Reduces time complexity to O(n) after computing the prefix sums.
• Elegant and uses combinatorial counting.

Cons:

• Requires careful handling of indices and modulo arithmetic.

Step-by-Step Walkthrough (Optimized Approach)

1. Initialize and Compute Prefix Sums:

   • Let n be the length of num.
   • Create an array (or simply a running counter) for prefix sums modulo 3.
   • Define prefix[0] = 0.
   • For every index i from 0 to n–1, update: [ prefix[i+1] = (prefix[i] + \text{int(num[i])}) \mod 3. ]

2. Count Frequency of Modulo Values:

   • Use a frequency array (or dictionary) freq with keys 0, 1, and 2.
   • For each value in the prefix array, increment the corresponding frequency.

3. Count Valid Substrings:

   • For each modulo value in {0, 1, 2}, if the frequency is f, then add
     [ \text{count} += \frac{f \times (f - 1)}{2} ] This counts the number of pairs of indices ((i, j)) where (i < j) and (prefix[i] = prefix[j]). Each such pair defines a substring (from index i to j-1) with a sum divisible by 3.

4. Return the Count:

   • The final count is the total number of divisible substrings.

Code Implementations

Python Code (Optimized Approach)