Find the Divisibility Array of a String

Medium
1245.

Find the Divisibility Array of a String

Find the Divisibility Array of a String is a medium coding problem on arrays, strings and math, asked in Amazon and Google interviews.

You are given a string word of n digits and a positive integer m.

The divisibility array div of word has length n: div[i] = 1 if the number written by the prefix word[0..i] is divisible by m, and div[i] = 0 otherwise.

Return the divisibility array. The prefixes can be far too long to fit in any integer type.

Example 1

Input
word = "1020", m = 10
Output
[0,1,0,1]
Explanation
The prefixes are 1, 10, 102 and 1020; only 10 and 1020 are multiples of 10.

Example 2

Input
word = "2026", m = 4
Output
[0,1,0,0]

Example 3

Input
word = "777", m = 7
Output
[1,1,1]

Constraints

  • 1 <= n <= 10^5
  • word.length == n
  • word consists of digits from 0 to 9
  • 1 <= m <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} word
 * @param {number} m
 * @return {number[]}
 */
var divisibilityArray = function(word, m) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find the Divisibility Array of a String — Problem & Solution

Find the Divisibility Array of a String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Find the Divisibility Array of a String is a medium coding problem on arrays, strings and math, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Strings, Math
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given a string word of n digits and a positive integer m.

The divisibility array div of word has length n: div[i] = 1 if the number written by the prefix word[0..i] is divisible by m, and div[i] = 0 otherwise.

Return the divisibility array. The prefixes can be far too long to fit in any integer type.

Example 1

Input: word = "1020", m = 10
Output: [0,1,0,1]
Explanation: The prefixes are 1, 10, 102 and 1020; only 10 and 1020 are multiples of 10.

Example 2

Input: word = "2026", m = 4
Output: [0,1,0,0]

Example 3

Input: word = "777", m = 7
Output: [1,1,1]

Constraints

  • 1 <= n <= 10^5
  • word.length == n
  • word consists of digits from 0 to 9
  • 1 <= m <= 10^9

Hints for Find the Divisibility Array of a String

  1. Hint 1

    You never need a prefix's full value — only its remainder modulo m.

  2. Hint 2

    If the prefix ending at i - 1 leaves remainder r, the next prefix is 10 × previous + digit.

  3. Hint 3

    So r = (r × 10 + digit) mod m. With m up to 10^9, r × 10 needs 64-bit arithmetic.

How to solve Find the Divisibility Array of a String

Carry the remainder of the current prefix modulo m; appending a digit multiplies the prefix by 10 and adds the digit, and remainders follow the same rule.

Approach

  1. Start with r = 0.
  2. For each digit d of word, set r = (r × 10 + d) mod m using a 64-bit integer.
  3. Append 1 to the answer if r == 0, otherwise 0.

Why it works

If P = q·m + r is the previous prefix, the new prefix is 10P + d = 10q·m + (10r + d), which has the same remainder as 10r + d. By induction r is always the true remainder of the current prefix, and the prefix is divisible exactly when that remainder is 0.

Complexity

  • Time — O(n)
  • Space — O(1) besides the output

Pitfalls

  • r is below 10^9, so r × 10 + 9 can reach about 10^10 — overflowing 32-bit integers.
  • Do not parse the prefix as a number; it can be 100,000 digits long.
  • A prefix of zeros is divisible by every m (its value is 0).

Reference solution

Python

from typing import List

def divisibilityArray(word: str, m: int) -> List[int]:
    r = 0
    out = []
    for ch in word:
        r = (r * 10 + ord(ch) - 48) % m
        out.append(1 if r == 0 else 0)
    return out

Java

public static int[] divisibilityArray(String word, int m) {
    int n = word.length();
    int[] out = new int[n];
    long r = 0;
    for (int i = 0; i < n; i++) {
        r = (r * 10 + (word.charAt(i) - '0')) % m;
        out[i] = r == 0 ? 1 : 0;
    }
    return out;
}

C++

vector<int> divisibilityArray(string word, int m) {
    vector<int> out(word.size());
    long long r = 0;
    for (size_t i = 0; i < word.size(); i++) {
        r = (r * 10 + (word[i] - '0')) % m;
        out[i] = r == 0 ? 1 : 0;
    }
    return out;
}

JavaScript

var divisibilityArray = function(word, m) {
    var r = 0, out = new Array(word.length);
    for (var i = 0; i < word.length; i++) {
        r = (r * 10 + (word.charCodeAt(i) - 48)) % m;
        out[i] = r === 0 ? 1 : 0;
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings