Find an integer that is common in the maximum number of given arithmetic progressions | C ++ implementation of the approach ; Function to return element common in maximum number of APs ; Initialize the count variable ; Increment count for every element of an AP ; Find the index with maximum count ; Return the maximum common element ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAXN  1000000 NEW_LINE int maxCommonElement ( int A [ ] , int D [ ] , int N ) { int cnt [ MAXN ] = { 0 } ; for ( int i = 0 ; i < N ; i ++ ) { for ( int j = A [ i ] ; j < MAXN ; j += D [ i ] ) cnt [ j ] ++ ; } int com = max_element ( cnt , cnt + MAXN ) - cnt ; return com ; } int main ( ) { int A [ ] = { 13 , 1 , 2 , 5 } , D [ ] = { 5 , 10 , 1 , 12 } ; int N = sizeof ( A ) / sizeof ( A [ 0 ] ) ; cout << maxCommonElement ( A , D , N ) ; return 0 ; }