title: Subsequences Size Three Array Whose Sum Divisible M 1
signature: func subsequencesSizeThreeArrayWhoseSumDivisibleM1(a []int, n int, m int) float64 {
test_code: package main
  
  import (
      "fmt"
      "reflect"
      "math"
      "sort"
  )
  
  // SOLUTION CODE
  // ===================================
  PLACEHOLDER_CODE_BODY
  
  // TESTING CODE
  // ===================================
  func validateSolution(actual float64, expected float64) bool {
      return math.Abs(actual - expected) < 1e-06
  }
  
  func driver(a []int, n int, m int, expected float64) string {
      if validateSolution(PLACEHOLDER_FN_NAME(a, n, m),expected) {
              return "PASSED"
      }
      return "FAILED"
  
  }
  
  func main() {
  
      // Use imports to avoid undefined errors
      var _ = reflect.DeepEqual
      _ = math.Abs
      _ = sort.Sort
      result := ""
      result = driver([]int{6, 7, 13, 16, 19, 20, 0, 4, 7, 10, 15, 17, 0, 2, 8, 12, 13, 14, 0, 0, 0, 2, 2, 2, 4, 8, 10, 73, 76, 78, 87, 90, 91, 99}, 
  	27, 
  	21, 75.0)
      fmt.Printf("TEST-0...%s\n", result)
      
      result = driver([]int{7, 13, 19, 15, 14, 11, 19, 4, 1, 18, 7, 5, 15, 9, 5, 11, 6, 18, 5, 19, 9, 7, 9, 19, 9, 12, 20, 12, 2, 66, 94, 12, 10, 4, 40, -72, 20, -2, -90, -90}, 
  	29, 
  	21, 0.0)
      fmt.Printf("TEST-1...%s\n", result)
      
      result = driver([]int{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, 
  	29, 
  	43, 1140.0)
      fmt.Printf("TEST-2...%s\n", result)
      
      result = driver([]int{1, 2, 3, 37, 91}, 
  	3, 
  	4, 0.0)
      fmt.Printf("TEST-3...%s\n", result)
      
      result = driver([]int{8, 6, 10, 10, 4, 2, 10, 2, 2, 10, 0, 8, 10, 86, 88}, 
  	13, 
  	12, 17.0)
      fmt.Printf("TEST-4...%s\n", result)
      
      result = driver([]int{1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1}, 
  	11, 
  	15, 56.0)
      fmt.Printf("TEST-5...%s\n", result)
      
      result = driver([]int{1, 2, 0, 2, 3, 0, 1, 58, 78}, 
  	7, 
  	4, 6.0)
      fmt.Printf("TEST-6...%s\n", result)
      
      result = driver([]int{0, 2, 2, 12, 4, 8, 8, 6, 10, 12, 10, 4, 4, -2, -4}, 
  	13, 
  	14, 12.0)
      fmt.Printf("TEST-7...%s\n", result)
      
      result = driver([]int{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, 
  	37, 
  	34, 286.0)
      fmt.Printf("TEST-8...%s\n", result)
      
      result = driver([]int{27, 1, 31, 14, 20, 8, 23, 12, 15, 0, 15, 26, 3, 8, 3, 26, 15, 31, 97, 90, 1, 69, 77, 20, 68, 11, 2, 92, 50, 8, 23, 83, 76, 6, 32, 43, 92}, 
  	18, 
  	35, 6.0)
      fmt.Printf("TEST-9...%s\n", result)
      
          
  }
source_py: def subsequences_size_three_array_whose_sum_divisible_m_1(A, N, M):
      ans = 0
      h = ([0] * M)
      for i in range(0, N):
          A[i] = (A[i] % M)
          h[A[i]] = (h[A[i]] + 1)
      for i in range(0, M):
          for j in range(i, M):
              rem = ((M - ((i + j) % M)) % M)
              if (rem < j):
                  continue
              if ((i == j) and (rem == j)):
                  ans = (ans + (((h[i] * (h[i] - 1)) * (h[i] - 2)) / 6))
              elif (i == j):
                  ans = (ans + (((h[i] * (h[i] - 1)) * h[rem]) / 2))
              elif (i == rem):
                  ans = (ans + (((h[i] * (h[i] - 1)) * h[j]) / 2))
              elif (rem == j):
                  ans = (ans + (((h[j] * (h[j] - 1)) * h[i]) / 2))
              else:
                  ans = (ans + ((h[i] * h[j]) * h[rem]))
          return ans
source_cpp: int subsequences_size_three_array_whose_sum_divisible_m_1(vector<int> A, int N, int M) {
    int ans = 0;
    int h [ M ] = {
      0 };
      for ( int i = 0;
      i < N;
      i ++ ) {
        A [ i ] = A [ i ] % M;
        h [ A [ i ] ] ++;
      }
      for ( int i = 0;
      i < M;
      i ++ ) {
        for ( int j = i;
        j < M;
        j ++ ) {
          int rem = ( M - ( i + j ) % M ) % M;
          if ( rem < j ) continue;
          if ( i == j && rem == j ) ans += h [ i ] * ( h [ i ] - 1 ) * ( h [ i ] - 2 ) / 6;
          else if ( i == j ) ans += h [ i ] * ( h [ i ] - 1 ) * h [ rem ] / 2;
          else if ( i == rem ) ans += h [ i ] * ( h [ i ] - 1 ) * h [ j ] / 2;
          else if ( rem == j ) ans += h [ j ] * ( h [ j ] - 1 ) * h [ i ] / 2;
          else ans = ans + h [ i ] * h [ j ] * h [ rem ];
        }
      }
      return ans;
    }