Find numbers of subarray of an array whose sum is divided by 3

Question

I got stuck in one algorithm question. Please suggest me some efficient algorithm for the below problem

Question is

Find numbers of subarrays(in range between 0 < R < N) whose sum is divisible by given number.

My approach:

Input:    0  5  3  8  2  1
Sum:   0  0  5  8 16 18 19
Mod 3: 0  0  2  2  1  0  1

No. of ways to chooses 0 , 1 or 2 is NC2

Problem: Is i am have asked to choose between some range i.e from 2 to 5 so array will become:

3  8  2  1

Does I have to recalculate the sum and Mod again or the original MOd array will give me a correct answer

Second Problem: What IF i change one element i.e 8 is change to 11 , How it will be effect

For the above problem I am considering using BIT dp[4][Max. Element] if mod is 0 update dp[0] if 1 update dp[1] so on How To update if VAlue at index is change

Answer 1

check this out:

this subroutine findes the largest subarray which its sum divided by 3. It goes only once over at the array with no extra space. here c++ code:

int largest_3_divider_subarray(int* a, int len){

int cum_sum            =  0;    
int index_of_first_one = -1;
int index_of_first_two = -1;
int absolute_maximal   =  0;
int current_maximal    =  0;
bool flag1 = 1, flag2 = 1;

for(int i = 0; i < len; ++i){

    cum_sum += a[i];

    switch (cum_sum%3)
    {
    case 1:
        if(flag1){
            index_of_first_one = i;
            flag1 = 0;
        }else       
            current_maximal = i - index_of_first_one;
        break;

    case 2:
        if(flag2){
            index_of_first_two = i;
            flag2 = 0;
        }else
            current_maximal = i - index_of_first_two;
        break;

    case 0:
        current_maximal = i;
    }

    if(current_maximal > absolute_maximal)
        absolute_maximal = current_maximal;
}

return absolute_maximal + 1;

}

int main() {

int A[]= {6,8,-2,0,9,13,1};
int k = largest_3_divider_subarray(A,7);


return 0;

}

Answer 2

It could be a running contest problem however there's a dp approach for that. you need to combine it with segment tree if you want to solve the running contest problem.

the basic idea:

• take care of %3 value of the sum of the digits of the substrings/subarrays which end at the current character/digit.
• Then take it as a subproblem and try to get the number of subarrays which end at the next character/digit with different mod values using the previously obtained data.

(characteristics of dp: we try to solve a subproblem then using the values obtained we try to solve a subproblem of bigger instance).

You just have to combine with segment trees if you want to solve the running contest problem in codechef

There are some good tutorials available for segment tree

Answer 3

public static int largest_3_divider_subarray(int a[]){

  int cum_sum            =  0;    
  int index_of_first_one = -1;
  int index_of_first_two = -1;
  int absolute_maximal   =  0;
  int current_maximal    =  0;
  boolean flag1 = true, flag2 = true;

  for(int i = 0; i < a.length; ++i){

     cum_sum += a[i];

     switch ((cum_sum%3))
     {
         case 1:
         case -2:
            if(flag1){
             index_of_first_one = i;
             flag1 = false;
            }else       
                current_maximal = i - index_of_first_one;
                break;

          case 2:
          case -1:
            if(flag2){
                index_of_first_two = i;
                flag2 = false;
            }else
                current_maximal = i - index_of_first_two;
                break;

          case 0:
                current_maximal = i+1;
            }

    if(current_maximal > absolute_maximal)
    absolute_maximal = current_maximal;
}

return absolute_maximal ;

}