Check if any valid sequence is divisible by M | C ++ program for the above approach ; Function to check if any valid sequence is divisible by M ; DEclare mod array ; Calculate the mod array ; Check if sum is divisible by M ; Check if sum is not divisible by 2 ; Remove the first element from the ModArray since it is not possible to place minus on the first element ; Decrease the size of array ; Sort the array ; Loop until the pointer cross each other ; Check if sum becomes equal ; Increase and decrease the pointer accordingly ; Driver code ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; void func ( int n , int m , int A [ ] ) { vector < int > ModArray ( n ) ; int sum = 0 ; for ( int i = 0 ; i < n ; i ++ ) { ModArray [ i ] = A [ i ] % m ; sum += ModArray [ i ] ; } sum = sum % m ; if ( sum % m == 0 ) { cout << " True " ; return ; } if ( sum % 2 != 0 ) { cout << " False " ; } else { ModArray . erase ( ModArray . begin ( ) ) ; int i = 0 ; int j = ModArray . size ( ) - 1 ; sort ( ModArray . begin ( ) , ModArray . end ( ) ) ; sum = sum / 2 ; int i1 , i2 ; while ( i <= j ) { int s = ModArray [ i ] + ModArray [ j ] ; if ( s == sum ) { i1 = i ; i2 = j ; cout << " True " ; break ; } else if ( s > sum ) j -- ; else i ++ ; } } } int main ( ) { int m = 2 ; int a [ ] = { 1 , 3 , 9 } ; int n = sizeof a / sizeof a [ 0 ] ; func ( n , m , a ) ; }