We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Divisibility Array of a String

Number: 2713

Difficulty: Medium

Paid? No

Companies: Google, Amazon

Problem Description

Given a 0-indexed string word composed of digits and a positive integer m, you need to return an array div where for each index i, div[i] is 1 if the numeric value of the prefix word[0...i] is divisible by m, otherwise 0.

Key Insights

  • Rather than converting large prefixes to integers (which can be computationally expensive), use modular arithmetic.
  • Compute the rolling modulus: for each digit, update mod = (mod * 10 + current_digit) % m.
  • Check if mod is zero after each update to determine divisibility.
  • The algorithm processes each digit in a single pass, making it efficient for long strings.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string. Space Complexity: O(n), for the output array that stores the divisibility flags.

Solution

We use a rolling modulus technique to check divisibility of each prefix without converting the entire prefix to an integer. By initializing a variable mod as 0, we update it for every digit using the relation mod = (mod * 10 + digit) % m. If at any step mod equals 0, the prefix is divisible by m and we mark that index with 1 in our result array. This approach avoids handling very large numbers and operates in a single pass through the string.

Code Solutions

def divisibilityArray(word, m):
    # Initialize mod as 0 to store the current modulus value
    mod = 0
    n = len(word)
    # Create a list to hold the divisibility values for each prefix
    div = [0] * n
    
    # Process every character in the string
    for i in range(n):
        # Convert the current character to an integer digit
        digit = int(word[i])
        # Update mod by incorporating the new digit
        mod = (mod * 10 + digit) % m
        # Check if the current prefix is divisible by m
        if mod == 0:
            div[i] = 1
        # Else, the value remains 0 as initialized
    
    # Return the computed divisibility array
    return div

# Example usage:
# print(divisibilityArray("998244353", 3))
← Back to All Questions