Skip to main content
Talentd

Find the Divisibility Array of a String - Solution & Explanation

MediumArrayMathString12 min readAsked at: Amazon, Google
Practice this problem

Problem Statement

You are given a 0-indexed string word of length n consisting of digits, and a positive integer m.

The divisibility array div of word is an integer array of length n such that:

  • div[i] = 1 if the numeric value of word[0,...,i] is divisible by m, or
  • div[i] = 0 otherwise.

Return the divisibility array of word.

 

Example 1:

Input: word = "998244353", m = 3
Output: [1,1,0,0,0,1,1,0,0]
Explanation: There are only 4 prefixes that are divisible by 3: "9", "99", "998244", and "9982443".

Example 2:

Input: word = "1010", m = 10
Output: [0,1,0,1]
Explanation: There are only 2 prefixes that are divisible by 10: "10", and "1010".

 

Constraints:

  • 1 <= n <= 105
  • word.length == n
  • word consists of digits from 0 to 9
  • 1 <= m <= 109

Approach Overview

Problem Overview: You are given a numeric string word and an integer m. For each prefix of the string, determine whether the number formed by that prefix is divisible by m. The result is a binary array where 1 means the prefix is divisible and 0 means it is not.

Approach 1: Iterative Modulo Calculation (O(n) time, O(1) space)

Construct the number incrementally while iterating through the string. Instead of converting the entire prefix into a large integer, maintain the current remainder using modular arithmetic. For each character, update the remainder with remainder = (remainder * 10 + digit) % m. If the remainder becomes 0, the current prefix is divisible by m, so record 1; otherwise record 0. This avoids large integer overflow and processes each character exactly once.

This approach relies on properties from math and sequential processing of a string. Since only the current remainder is stored, space usage stays constant. This is the optimal solution and scales efficiently even when the string length is up to 10^5.

Approach 2: Prefix Construction with BigInteger (O(n^2) time, O(n) space)

Another method builds each prefix number explicitly using a big integer representation. At every step, append the new digit to the previous value using a BigInteger (in Java) and check divisibility using mod. This works because big integer libraries support arbitrary precision arithmetic.

The drawback is that the prefix value grows with every digit. Each arithmetic operation becomes more expensive as the number length increases, leading to roughly O(n^2) total time in practice. Memory usage also grows because the full prefix number must be stored. This approach is easier to reason about conceptually but inefficient for long inputs.

Recommended for interviews: The iterative modulo approach is the expected solution. It demonstrates understanding of modular arithmetic and efficient prefix processing. Interviewers want to see that you avoid constructing huge integers and instead track the remainder while iterating through the array-like structure of digits. Mentioning the BigInteger approach first can show baseline thinking, but implementing the modulo trick proves strong algorithmic intuition.

Approach 1: Iterative Modulo Calculation

Iterative Modulo Calculation: In this approach, we iterate through the string and maintain a running computation of the numeric value of the prefix modulo m. By keeping track of this value, we can determine if the current prefix is divisible by m without fully computing its numeric value (which could be large). This method efficiently checks divisibility by taking advantage of the mathematical properties of the modulo operation.

This C implementation iterates over each character in the given word, updating the prefix's numeric value modulo m. It determines if each prefix is divisible by m by checking if the modulo result is zero. The results are stored in the result array.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) - we traverse the string once.
Space Complexity: O(n) - the result array takes additional space.

Try this approach in the editor →

Approach 2: Prefix Sum with BigInteger

Prefix Sum with BigInteger: This approach is useful when handling very large numbers that standard integer types cannot accommodate. By using big integer libraries or constructs, we can compute the prefix sum directly by considering each prefix as a whole number and using higher precision arithmetic to handle larger values. In languages where native big integer support is available, we leverage this capability to simplify our implementation.

This Java solution applies BigInteger for operations to manage very large prefix values. Such robust arithmetic ensures accuracy over potential integer overflow.

Code

Java

Java

Complexity

Time Complexity: O(n) per arithmetic operation (though potentially slower due to BigInteger)
Space Complexity: O(n)

Try this approach in the editor →

Approach 3: Traversal + Modulo

We iterate over the string word, using a variable x to record the modulo result of the current prefix with m. If x is 0, then the divisible array value at the current position is 1, otherwise it is 0.

The time complexity is O(n), where n is the length of the string word. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRustC

Python

Java

C++

Go

TypeScript

Rust

C

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Iterative Modulo Calculation

Time Complexity: O(n) - we traverse the string once.
Space Complexity: O(n) - the result array takes additional space.

Prefix Sum with BigInteger

Time Complexity: O(n) per arithmetic operation (though potentially slower due to BigInteger)
Space Complexity: O(n)

Traversal + Modulo—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Iterative Modulo CalculationO(n)O(1)Best for large strings and interview settings; avoids large integer construction
Prefix with BigIntegerO(n^2)O(n)Useful when demonstrating the direct numeric interpretation of prefixes using arbitrary precision integers

Video Solution

Leetcode Weekly contest 334 - Medium - Find the Divisibility Array of a String • Prakhar Agrawal • 803 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find the Divisibility Array of a String easy or hard?
Find the Divisibility Array of a String is typically classified as a Medium problem. The challenge lies in recognizing that constructing full prefix numbers is inefficient and that modular arithmetic can track divisibility efficiently in O(n) time.
Find the Divisibility Array of a String Python/Java solution
In Python or Java, iterate through the string and maintain a running remainder variable. Update it with modular arithmetic and append 1 or 0 to the result depending on whether the remainder becomes zero. The same logic works across Python, Java, C++, JavaScript, and C#.
How to solve Find the Divisibility Array of a String in O(n)?
Iterate through the digits of the string and keep a running remainder. At each step compute remainder = (remainder * 10 + currentDigit) % m. If the remainder equals 0, mark the corresponding index in the result array as 1; otherwise mark it as 0. This processes all prefixes in a single pass.
What is the best approach for Find the Divisibility Array of a String?
The best approach is iterative modulo calculation. Maintain the current remainder while scanning the string and update it with (remainder * 10 + digit) % m. This determines whether each prefix is divisible without building large numbers. The algorithm runs in O(n) time and O(1) space.
Is Find the Divisibility Array of a String asked at Google/Amazon/Meta?
Problems involving prefix processing and modular arithmetic frequently appear in interviews at companies like Google, Amazon, and Meta. While this exact problem may vary, the pattern of maintaining rolling remainders over strings or arrays is a common interview concept.
What data structure is used in Find the Divisibility Array of a String?
The problem mainly uses arrays and strings. The result is stored in an array, while the input is processed as a string of digits. The algorithm relies on modular arithmetic rather than complex data structures.
What is the time complexity of Find the Divisibility Array of a String?
The optimal solution runs in O(n) time where n is the length of the string. Each digit is processed once and the remainder is updated using constant-time modular arithmetic. Space complexity is O(1) excluding the output array.

Ready to solve this problem?

Practice Find the Divisibility Array of a String with our built-in code editor and test cases.

Practice on FleetCode
Previous

Make Sum Divisible by P

Next

Subarray Sums Divisible by K