How to find number of Multiples of 3

Question

This was a contest Q:

There are N numbers a[0],a[1]..a[N - 1]. Initally all are 0. You have to perform two types of operations :

1. Increase the numbers between indices A and B by 1. This is represented by the command "0 A B"
2. Answer how many numbers between indices A and B are divisible by 3. This is represented by the command "1 A B".

Input : The first line contains two integers, N and Q.

Each of the next Q lines are either of the form "0 A B" or "1 A B" as mentioned above.

Output : Output 1 line for each of the queries of the form "1 A B" containing the required answer for the corresponding query.

Sample Input :

4 7 1 0 3 0 1 2 0 1 3 1
0 0 0 0 3 1 3 3 1 0 3

Sample Output :

4 1 0 2

Constraints :

1 <= N <= 100000 1 <= Q <= 100000 0 <= A <= B <= N - 1

I have no idea how to solve this. can you help please?

The time limit is 1 second. I tried brute force and i also tried saving number of divisors of 3 coming before ith element for each i.

here's my C code:

#include <stdio.h>


int nums[100*1000+20];
int d[100*1000+20];
int e[100*1000+20];
int dah[100*1000+20];

int main()
{
    int n,q;
    scanf("%d%d",&n,&q);
    int h;
    for(h=0;h<n;h++)
        {d[h/100]++; e[h/1000]++; dah[h/10]++;}
    int test;
    for(test=0;test<q;test++)
    {
        int op,start,end;
        scanf("%d%d%d",&op,&start,&end);
        if(0==op)
        {
            int x;
            for(x=start;x<=end;x++)
            {
                nums[x]++;
                nums[x]%=3;
                if(nums[x]==0)
                {
                    d[x/100]++;
                    e[x/1000]++;
                    dah[x/10]++;
                }
                else if(nums[x]==1)
                {
                    d[x/100]--;
                    e[x/1000]--;
                    dah[x/10]--;
                }
            }
        }
        else if(1==op)
        {
            int f;
            int ans=0;
            for(f=start;f<=end;)
            {
                if(f%1000==0&&f+1000<end)
                {
                    ans+=e[f/1000];
                    f+=1000;
                }
                else if(f%100==0&&f+100<end)
                {
                    ans+=d[f/100];
                    f+=100;
                }
                else if(f%10==0&&f+10<end)
                {
                    ans+=dah[f/10];
                    f+=10;
                }
                else
                {
                    ans+=(nums[f]==0);
                    f++;
                }
            }
            printf("%d\n",ans);
        }
    }
    return 0;
}

In this approach I save number of multiples of 3 between k*1000 and (k+1)*1000 and also the same thing for k*100 and (k+1)*100 and also for 10. this helps me query faster. but this yet gives me time limit exceed.

Answer 1

what's the upper bound for your array? first, figure that out. Then, plan on reading lines of input in one of those two forms. The lines in format 0 A B are easy to handle, can you code at least that much? If so, post it and then worry about the lines in format 1 A B.

Answer 2

Hint #1:

Think about how you might use the MODULUS operator to help you. Initially, you have N numbers, let's say N is 5.

So we can store the remainders for each number (i.e. store 0 MOD 3, 1 MOD 3, 2 MOD 3, and so on):

a[0] = 0
a[1] = 1
a[2] = 2
a[3] = 0
a[4] = 1
a[5] = 2

Each time you increment a range of numbers between A and B, you really only need to store a 0, 1, or 2 in the array. For example, if we are incrementing 2, then the new number will be 3. That is now divisible by 3, so we store 0 in the array. So in cases where we have 0 and we increment, we store 1, if we have 1 we store 2, and if we have 2 we store 0.

This optimization eliminates the need to do any division except for the initial step. Division is a very expensive operation, which is why we want to eliminate it where we can.

So after incrementing 0 through 5, the array would look like this:

a[0] = 1
a[1] = 2
a[2] = 0
a[3] = 1
a[4] = 2
a[5] = 0

The amount of numbers between A and B that are divisible by 3 is just the number of elements that have 0 (2 in this case).

Now you have to think about how to query a range A through B efficiently to find the amount of numbers divisible by 3.

Hint #2:

To find out how many numbers over the interval [A,B] are divisible by 3, one algorithm/data structure you can consider using is a segment tree. Read about it here. What this buys you is that now you can compute the amount of numbers divisible by 3 for any such interval [A,B] very quickly, instead of looping over the array and having to count them.

Answer 3

If, as your title suggests, you aren't sure how to tell if a number is divisible by three then I suggest you have a look into the modulus operation, in the languages I'm most familiar with it is represented using a %.

Answer 4

Hint #3:

Good suggestion by dcp. Though it doesn't reveal how to solve the problem. It's not necessary to store all numbers MOD 3 in the array. If the numbers are updated every time in the array the complexity is O(Q * N) which is obviously too much for given N, Q and 1 sec. in the worst case. That is the point of Ali in the comment to dcp suggestion.

The number of integers with MOD%0, MOD%1, MOD%2 can be stored in each node of the segment tree. Hence the updates can be done in O(log N), which results in O(Q log N) for updates only. For each query the same complexity O(log N) applies. Since you know the number of integers MOD%3 for each residue, it's not necessary to go down to all leaves (each leave in segment tree corresponds to array element) to figure how many numbers are divisible by 3. Once you understand how segment tree works that should be obvious why it is necessary to store residues in each node of the segment tree. Overall complexity of the algorithm is O(Q log N) which will fit nicely in 1 sec. time limit.

When going down the segment tree be sure to accumulate number of integers per residue, for each segment that you visit on the way down the tree.