Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2575.html

2575. Find the Divisibility Array of a String

Description

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

Solutions

Solution 1: 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)$.

  • class Solution {
        public int[] divisibilityArray(String word, int m) {
            int n = word.length();
            int[] ans = new int[n];
            long x = 0;
            for (int i = 0; i < n; ++i) {
                x = (x * 10 + word.charAt(i) - '0') % m;
                if (x == 0) {
                    ans[i] = 1;
                }
            }
            return ans;
        }
    }
    
  • class Solution {
    public:
        vector<int> divisibilityArray(string word, int m) {
            vector<int> ans;
            long long x = 0;
            for (char& c : word) {
                x = (x * 10 + c - '0') % m;
                ans.push_back(x == 0 ? 1 : 0);
            }
            return ans;
        }
    };
    
  • class Solution:
        def divisibilityArray(self, word: str, m: int) -> List[int]:
            ans = []
            x = 0
            for c in word:
                x = (x * 10 + int(c)) % m
                ans.append(1 if x == 0 else 0)
            return ans
    
    
  • func divisibilityArray(word string, m int) (ans []int) {
    	x := 0
    	for _, c := range word {
    		x = (x*10 + int(c-'0')) % m
    		if x == 0 {
    			ans = append(ans, 1)
    		} else {
    			ans = append(ans, 0)
    		}
    	}
    	return ans
    }
    
  • function divisibilityArray(word: string, m: number): number[] {
        const ans: number[] = [];
        let x = 0;
        for (const c of word) {
            x = (x * 10 + Number(c)) % m;
            ans.push(x === 0 ? 1 : 0);
        }
        return ans;
    }
    
    
  • impl Solution {
        pub fn divisibility_array(word: String, m: i32) -> Vec<i32> {
            let m = m as i64;
            let mut x = 0i64;
            word.as_bytes()
                .iter()
                .map(|&c| {
                    x = (x * 10 + i64::from(c - b'0')) % m;
                    if x == 0 {
                        1
                    } else {
                        0
                    }
                })
                .collect()
        }
    }
    
    

All Problems

All Solutions