Welcome to Subscribe On Youtube

3525. Find X Value of Array II

Description

You are given an array of positive integers nums and a positive integer k. You are also given a 2D array queries, where queries[i] = [indexi, valuei, starti, xi].

You are allowed to perform an operation once on nums, where you can remove any suffix from nums such that nums remains non-empty.

The x-value of nums for a given x is defined as the number of ways to perform this operation so that the product of the remaining elements leaves a remainder of x modulo k.

For each query in queries you need to determine the x-value of nums for xi after performing the following actions:

  • Update nums[indexi] to valuei. Only this step persists for the rest of the queries.
  • Remove the prefix nums[0..(starti - 1)] (where nums[0..(-1)] will be used to represent the empty prefix).

Return an array result of size queries.length where result[i] is the answer for the ith query.

A prefix of an array is a subarray that starts from the beginning of the array and extends to any point within it.

A suffix of an array is a subarray that starts at any point within the array and extends to the end of the array.

Note that the prefix and suffix to be chosen for the operation can be empty.

Note that x-value has a different definition in this version.

 

Example 1:

Input: nums = [1,2,3,4,5], k = 3, queries = [[2,2,0,2],[3,3,3,0],[0,1,0,1]]

Output: [2,2,2]

Explanation:

  • For query 0, nums becomes [1, 2, 2, 4, 5], and the empty prefix must be removed. The possible operations are:
    • Remove the suffix [2, 4, 5]. nums becomes [1, 2].
    • Remove the empty suffix. nums becomes [1, 2, 2, 4, 5] with a product 80, which gives remainder 2 when divided by 3.
  • For query 1, nums becomes [1, 2, 2, 3, 5], and the prefix [1, 2, 2] must be removed. The possible operations are:
    • Remove the empty suffix. nums becomes [3, 5].
    • Remove the suffix [5]. nums becomes [3].
  • For query 2, nums becomes [1, 2, 2, 3, 5], and the empty prefix must be removed. The possible operations are:
    • Remove the suffix [2, 2, 3, 5]. nums becomes [1].
    • Remove the suffix [3, 5]. nums becomes [1, 2, 2].

Example 2:

Input: nums = [1,2,4,8,16,32], k = 4, queries = [[0,2,0,2],[0,2,0,1]]

Output: [1,0]

Explanation:

  • For query 0, nums becomes [2, 2, 4, 8, 16, 32]. The only possible operation is:
    • Remove the suffix [2, 4, 8, 16, 32].
  • For query 1, nums becomes [2, 2, 4, 8, 16, 32]. There is no possible way to perform the operation.

Example 3:

Input: nums = [1,1,2,1,1], k = 2, queries = [[2,1,0,1]]

Output: [5]

 

Constraints:

  • 1 <= nums[i] <= 109
  • 1 <= nums.length <= 105
  • 1 <= k <= 5
  • 1 <= queries.length <= 2 * 104
  • queries[i] == [indexi, valuei, starti, xi]
  • 0 <= indexi <= nums.length - 1
  • 1 <= valuei <= 109
  • 0 <= starti <= nums.length - 1
  • 0 <= xi <= k - 1

Solutions

Solution 1

  • class Node {
    int l, r, prod;
    int[] cnt;

    Node(int l, int r, int k) {
        this.l = l;
        this.r = r;
        this.prod = 1;
        this.cnt = new int[k];
    }
}

class SegmentTree {
    private int k;
    private Node[] tr;

    SegmentTree(int[] nums, int k) {
        this.k = k;
        int n = nums.length;
        tr = new Node[n << 2];
        build(1, 1, n, nums);
    }

    private Node merge(Node a, Node b) {
        Node c = new Node(0, 0, k);
        c.prod = a.prod * b.prod % k;
        System.arraycopy(a.cnt, 0, c.cnt, 0, k);
        for (int r = 0; r < k; ++r) {
            c.cnt[a.prod * r % k] += b.cnt[r];
        }
        return c;
    }

    private void pushup(int u) {
        Node p = merge(tr[u << 1], tr[u << 1 | 1]);
        tr[u].prod = p.prod;
        tr[u].cnt = p.cnt;
    }

    private void build(int u, int l, int r, int[] nums) {
        tr[u] = new Node(l, r, k);
        if (l == r) {
            int v = nums[l - 1] % k;
            tr[u].prod = v;
            tr[u].cnt[v] = 1;
            return;
        }
        int mid = (l + r) >> 1;
        build(u << 1, l, mid, nums);
        build(u << 1 | 1, mid + 1, r, nums);
        pushup(u);
    }

    void modify(int u, int x, int v) {
        if (tr[u].l == tr[u].r) {
            v %= k;
            tr[u].prod = v;
            Arrays.fill(tr[u].cnt, 0);
            tr[u].cnt[v] = 1;
            return;
        }
        int mid = (tr[u].l + tr[u].r) >> 1;
        if (x <= mid) {
            modify(u << 1, x, v);
        } else {
            modify(u << 1 | 1, x, v);
        }
        pushup(u);
    }

    Node query(int u, int l, int r) {
        if (tr[u].l >= l && tr[u].r <= r) {
            return tr[u];
        }
        int mid = (tr[u].l + tr[u].r) >> 1;
        if (r <= mid) {
            return query(u << 1, l, r);
        }
        if (l > mid) {
            return query(u << 1 | 1, l, r);
        }
        return merge(query(u << 1, l, r), query(u << 1 | 1, l, r));
    }
}

class Solution {
    public int[] resultArray(int[] nums, int k, int[][] queries) {
        int n = nums.length;
        SegmentTree tree = new SegmentTree(nums, k);
        int[] ans = new int[queries.length];
        for (int i = 0; i < queries.length; ++i) {
            int idx = queries[i][0], val = queries[i][1], start = queries[i][2], x = queries[i][3];
            tree.modify(1, idx + 1, val);
            ans[i] = tree.query(1, start + 1, n).cnt[x];
        }
        return ans;
    }
}


  • class Node {
public:
    int l = 0, r = 0;
    int prod = 1;
    int cnt[5]{};
};

class SegmentTree {
public:
    SegmentTree(vector<int>& nums, int k) {
        this->k = k;
        int n = nums.size();
        tr.resize(n << 2);
        build(1, 1, n, nums);
    }

    void modify(int u, int x, int v) {
        if (tr[u].l == tr[u].r) {
            v %= k;
            tr[u].prod = v;
            memset(tr[u].cnt, 0, sizeof(tr[u].cnt));
            tr[u].cnt[v] = 1;
            return;
        }
        int mid = (tr[u].l + tr[u].r) >> 1;
        if (x <= mid) {
            modify(u << 1, x, v);
        } else {
            modify(u << 1 | 1, x, v);
        }
        pushup(u);
    }

    Node query(int u, int l, int r) {
        if (tr[u].l >= l && tr[u].r <= r) {
            return tr[u];
        }
        int mid = (tr[u].l + tr[u].r) >> 1;
        if (r <= mid) {
            return query(u << 1, l, r);
        }
        if (l > mid) {
            return query(u << 1 | 1, l, r);
        }
        return merge(query(u << 1, l, r), query(u << 1 | 1, l, r));
    }

private:
    int k;
    vector<Node> tr;

    Node merge(const Node& a, const Node& b) {
        Node c;
        c.prod = a.prod * b.prod % k;
        memcpy(c.cnt, a.cnt, sizeof(c.cnt));
        for (int r = 0; r < k; ++r) {
            c.cnt[a.prod * r % k] += b.cnt[r];
        }
        return c;
    }

    void pushup(int u) {
        Node p = merge(tr[u << 1], tr[u << 1 | 1]);
        tr[u].prod = p.prod;
        memcpy(tr[u].cnt, p.cnt, sizeof(tr[u].cnt));
    }

    void build(int u, int l, int r, vector<int>& nums) {
        tr[u].l = l;
        tr[u].r = r;
        if (l == r) {
            int v = nums[l - 1] % k;
            tr[u].prod = v;
            tr[u].cnt[v] = 1;
            return;
        }
        int mid = (l + r) >> 1;
        build(u << 1, l, mid, nums);
        build(u << 1 | 1, mid + 1, r, nums);
        pushup(u);
    }
};

class Solution {
public:
    vector<int> resultArray(vector<int>& nums, int k, vector<vector<int>>& queries) {
        int n = nums.size();
        SegmentTree tree(nums, k);
        vector<int> ans;
        ans.reserve(queries.size());
        for (auto& q : queries) {
            tree.modify(1, q[0] + 1, q[1]);
            ans.push_back(tree.query(1, q[2] + 1, n).cnt[q[3]]);
        }
        return ans;
    }
};


  • class Node:
    __slots__ = "l", "r", "prod", "cnt"

    def __init__(self, l: int, r: int, k: int):
        self.l = l
        self.r = r
        self.prod = 1
        self.cnt = [0] * k


class SegmentTree:
    __slots__ = "k", "tr"

    def __init__(self, nums: list[int], k: int):
        self.k = k
        n = len(nums)
        self.tr = [None] * (n << 2)
        self.build(1, 1, n, nums)

    def merge(self, a: Node, b: Node) -> tuple[int, list[int]]:
        k = self.k
        prod = a.prod * b.prod % k
        cnt = a.cnt[:]
        for r, c in enumerate(b.cnt):
            cnt[a.prod * r % k] += c
        return prod, cnt

    def pushup(self, u: int):
        prod, cnt = self.merge(self.tr[u << 1], self.tr[u << 1 | 1])
        self.tr[u].prod = prod
        self.tr[u].cnt = cnt

    def build(self, u: int, l: int, r: int, nums: list[int]):
        self.tr[u] = Node(l, r, self.k)
        if l == r:
            v = nums[l - 1] % self.k
            self.tr[u].prod = v
            self.tr[u].cnt[v] = 1
            return
        mid = (l + r) >> 1
        self.build(u << 1, l, mid, nums)
        self.build(u << 1 | 1, mid + 1, r, nums)
        self.pushup(u)

    def modify(self, u: int, x: int, v: int):
        if self.tr[u].l == self.tr[u].r:
            v %= self.k
            self.tr[u].prod = v
            self.tr[u].cnt = [0] * self.k
            self.tr[u].cnt[v] = 1
            return
        mid = (self.tr[u].l + self.tr[u].r) >> 1
        if x <= mid:
            self.modify(u << 1, x, v)
        else:
            self.modify(u << 1 | 1, x, v)
        self.pushup(u)

    def query(self, u: int, l: int, r: int) -> Node:
        if self.tr[u].l >= l and self.tr[u].r <= r:
            return self.tr[u]
        mid = (self.tr[u].l + self.tr[u].r) >> 1
        if r <= mid:
            return self.query(u << 1, l, r)
        if l > mid:
            return self.query(u << 1 | 1, l, r)
        left = self.query(u << 1, l, r)
        right = self.query(u << 1 | 1, l, r)
        prod, cnt = self.merge(left, right)
        res = Node(0, 0, self.k)
        res.prod = prod
        res.cnt = cnt
        return res


class Solution:
    def resultArray(
        self, nums: list[int], k: int, queries: list[list[int]]
    ) -> list[int]:
        n = len(nums)
        tree = SegmentTree(nums, k)
        ans = []
        for idx, val, start, x in queries:
            tree.modify(1, idx + 1, val)
            ans.append(tree.query(1, start + 1, n).cnt[x])
        return ans


  • type node struct {
	l, r, prod int
	cnt        []int
}

type segmentTree struct {
	k  int
	tr []*node
}

func newSegmentTree(nums []int, k int) *segmentTree {
	n := len(nums)
	tr := make([]*node, n<<2)
	t := &segmentTree{k, tr}
	t.build(1, 1, n, nums)
	return t
}

func (t *segmentTree) merge(a, b *node) *node {
	c := &node{prod: a.prod * b.prod % t.k, cnt: make([]int, t.k)}
	copy(c.cnt, a.cnt)
	for r, v := range b.cnt {
		c.cnt[a.prod*r%t.k] += v
	}
	return c
}

func (t *segmentTree) pushup(u int) {
	p := t.merge(t.tr[u<<1], t.tr[u<<1|1])
	t.tr[u].prod = p.prod
	copy(t.tr[u].cnt, p.cnt)
}

func (t *segmentTree) build(u, l, r int, nums []int) {
	t.tr[u] = &node{l: l, r: r, prod: 1, cnt: make([]int, t.k)}
	if l == r {
		v := nums[l-1] % t.k
		t.tr[u].prod = v
		t.tr[u].cnt[v] = 1
		return
	}
	mid := (l + r) >> 1
	t.build(u<<1, l, mid, nums)
	t.build(u<<1|1, mid+1, r, nums)
	t.pushup(u)
}

func (t *segmentTree) modify(u, x, v int) {
	if t.tr[u].l == t.tr[u].r {
		v %= t.k
		t.tr[u].prod = v
		for i := range t.tr[u].cnt {
			t.tr[u].cnt[i] = 0
		}
		t.tr[u].cnt[v] = 1
		return
	}
	mid := (t.tr[u].l + t.tr[u].r) >> 1
	if x <= mid {
		t.modify(u<<1, x, v)
	} else {
		t.modify(u<<1|1, x, v)
	}
	t.pushup(u)
}

func (t *segmentTree) query(u, l, r int) *node {
	if t.tr[u].l >= l && t.tr[u].r <= r {
		return t.tr[u]
	}
	mid := (t.tr[u].l + t.tr[u].r) >> 1
	if r <= mid {
		return t.query(u<<1, l, r)
	}
	if l > mid {
		return t.query(u<<1|1, l, r)
	}
	return t.merge(t.query(u<<1, l, r), t.query(u<<1|1, l, r))
}

func resultArray(nums []int, k int, queries [][]int) []int {
	n := len(nums)
	tree := newSegmentTree(nums, k)
	ans := make([]int, len(queries))
	for i, q := range queries {
		tree.modify(1, q[0]+1, q[1])
		ans[i] = tree.query(1, q[2]+1, n).cnt[q[3]]
	}
	return ans
}


  • class Node {
    l: number;
    r: number;
    prod: number;
    cnt: number[];

    constructor(l: number, r: number, k: number) {
        this.l = l;
        this.r = r;
        this.prod = 1;
        this.cnt = Array(k).fill(0);
    }
}

class SegmentTree {
    private k: number;
    private tr: Node[];

    constructor(nums: number[], k: number) {
        this.k = k;
        this.tr = Array(nums.length << 2);
        this.build(1, 1, nums.length, nums);
    }

    private merge(a: Node, b: Node): Node {
        const c = new Node(0, 0, this.k);
        c.prod = (a.prod * b.prod) % this.k;
        c.cnt = a.cnt.slice();
        for (let r = 0; r < this.k; ++r) {
            c.cnt[(a.prod * r) % this.k] += b.cnt[r];
        }
        return c;
    }

    private pushup(u: number): void {
        const p = this.merge(this.tr[u << 1], this.tr[(u << 1) | 1]);
        this.tr[u].prod = p.prod;
        this.tr[u].cnt = p.cnt;
    }

    private build(u: number, l: number, r: number, nums: number[]): void {
        this.tr[u] = new Node(l, r, this.k);
        if (l === r) {
            const v = nums[l - 1] % this.k;
            this.tr[u].prod = v;
            this.tr[u].cnt[v] = 1;
            return;
        }
        const mid = (l + r) >> 1;
        this.build(u << 1, l, mid, nums);
        this.build((u << 1) | 1, mid + 1, r, nums);
        this.pushup(u);
    }

    modify(u: number, x: number, v: number): void {
        if (this.tr[u].l === this.tr[u].r) {
            v %= this.k;
            this.tr[u].prod = v;
            this.tr[u].cnt.fill(0);
            this.tr[u].cnt[v] = 1;
            return;
        }
        const mid = (this.tr[u].l + this.tr[u].r) >> 1;
        if (x <= mid) {
            this.modify(u << 1, x, v);
        } else {
            this.modify((u << 1) | 1, x, v);
        }
        this.pushup(u);
    }

    query(u: number, l: number, r: number): Node {
        if (this.tr[u].l >= l && this.tr[u].r <= r) {
            return this.tr[u];
        }
        const mid = (this.tr[u].l + this.tr[u].r) >> 1;
        if (r <= mid) {
            return this.query(u << 1, l, r);
        }
        if (l > mid) {
            return this.query((u << 1) | 1, l, r);
        }
        return this.merge(this.query(u << 1, l, r), this.query((u << 1) | 1, l, r));
    }
}

function resultArray(nums: number[], k: number, queries: number[][]): number[] {
    const n = nums.length;
    const tree = new SegmentTree(nums, k);
    const ans: number[] = [];
    for (const [idx, val, start, x] of queries) {
        tree.modify(1, idx + 1, val);
        ans.push(tree.query(1, start + 1, n).cnt[x]);
    }
    return ans;
}

All Problems

All Solutions