Problem 18

One comment on “Problem 18”


  • Prajwal

    // approach:
    // if remainder of any two no’s is k, then sum of those 2 divisible by k
    // sum of elements having remainders i and k-i also divisible by k as i+k-i=k
    // if k is even then i and k-i will be same i.e k/2 so sum of them will be k i.e divisible again so we should add only min(1, a[k/2]);
    // if any no. having remainder zero then sum of such no. will also have remainder zero i.e will become divisible by k so we should add
    // only min(1, a[0]);

    int main(){
    int, n, k, a[], retur_n; //a[] for storing remainders
    cin>>n>>k;
    for(int i=0; i>ai;
    ++a[ai];
    }

    if(k%2==0){

    a[k/2]=min(1, a[k/2]);
    retur_n=0;

    for(int i=1; i<k/2; i++){
    retur_n+=max(a[i], a[k-i]);
    }
    retur_n+=min(1, a[0]);
    cout<<"the size of maximal subset of S is"<<retur_n<<endl;
    }
    }