LeetCode Entry

3524. Find X Value of Array I

21.09.2026 medium 2026 kotlin rust

Count subarrays product%k = x for x in 0..

3524. Find X Value of Array I medium substack youtube

https://dmitrysamoylenko.com/leetcode/

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1489

Problem TLDR

Count subarrays product%k = x for x in 0..<k

Intuition

Track count of subarrays so far in [k] array. The new reminder after adding n to each subarray for each x in 0..<k is the v=xn%k. Increment all the subarrays ending by v cnt[v] += cnt[i] by count of all subarrays ending by i that now added number n to them making the product reminder in%k

Approach

• look at others people answers i guess

Complexity

• Time complexity: \(O(nk)\)

• Space complexity: \(O(k)\)

Code

    fun resultArray(n: IntArray, k: Int) = LongArray(k).also { res ->
        var c = IntArray(k)
        for (x in n) c = IntArray(k).also {
            it[x % k]++; res[x % k]++
            for (i in 0..<k) {
                val v = (1L * i * x % k).toInt()
                it[v] += c[i]; res[v] += c[i]
            }
        }
    }

    pub fn result_array(n: Vec<i32>, k: i32) -> Vec<i64> {
        let k = k as usize; let (mut res, mut c) = (vec![0; k], vec![0; k]);
        for x in n {
            let (mut next, x) = (vec![0; k], x as usize % k);
            next[x] += 1; res[x] += 1;
            for (i, cnt) in (0..).zip(c) {
                let v = i * x % k; next[v] += cnt; res[v] += cnt as i64
            } c = next
        } res
    }