Introduction

In this blog post, we will explore how to solve the LeetCode problem "2575" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

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

Explanation

Here's the breakdown of the solution:

• Incremental Calculation: We iterate through the word string, building the numeric value of the prefix incrementally.
• Modulo Operator: At each step, we use the modulo operator (%) to keep the prefix value within manageable bounds, preventing potential overflow issues and improving efficiency.

• Divisibility Check: We check if the current prefix value is divisible by m using the modulo operator.

• Runtime Complexity: O(n), where n is the length of the word.

• Storage Complexity: O(n) for the div array.

Code

    def divisibilityArray(word: str, m: int) -> list[int]:
    n = len(word)
    div = [0] * n
    prefix_val = 0
    for i in range(n):
        prefix_val = (prefix_val * 10 + int(word[i])) % m
        if prefix_val == 0:
            div[i] = 1
        else:
            div[i] = 0
    return div