Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

Dontony's blog

By Dontony, history, 3 years ago, In English

Q:You are given an array of n elements. Now, there are 2 types of queries on the array. 1) Change the element at index i to some new element(say x). 2)Given l and r ,find the number of subarrays in range l to r having sum divisible by 3. The number of queries can be upto 1e5 and also size of the array can be upto 1e5.

This is not from some ongoing coding contest. I found this question on gfg from a company's interview experience. Link to that blog:- https://www.geeksforgeeks.org/nutanix-interview-experience-for-mts-intern-off-campus-2021/

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

You need to know for some segment, how many subarrays have $$$ sum \% 3 = 0 $$$. In order to do so, you can keep on each segment tree node, how many subarrays, preffixes and suffixes has that segment, such that their $$$ sum \% 3 = k $$$, for k = 0, 1, 2.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yupp,I also got it now. But this would be pretty much implementation heavy right? Storing how many subarrays ,prefix, suffix, sum modulo 3 for that range for each 0,1 and 2

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Yup, it's really annoying to code.

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

(I'm making the assumption that a[i] can't be zero)

Create a range sum segment tree on prefix sum array of given array A[] and in each node of the segment tree you will store the node value % 3, Now for a subarray [L, R] sum to be divisible by 3, sum of subarray A[0, L-1] % 3 should be equal to sum of subarray A[0, R] % 3,

So you can store the count of 0, 1 and 2's in each node and based on that you can count the total number of possible subarrays with sum % 3 == 0.

You should be able to handle the updates part yourself now I think

Feel free to correct me in case I missed something :)

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If a[i]=0, how does that make things different. Btw for updates, u need a lazy segtree to count and update the prefix sums right?

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      On second thought A[i] == 0 shouldn't affect the solution, and yah you need lazy for range updates

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You only have point updates in this problem.