Modulo strength , want explanation in the algorithm used to compute the answer

Question

I was trying to solve the problem Modulo strength at hackerearth ,
https://www.hackerearth.com/practice/basic-programming/implementation/basics-of-implementation/practice-problems/golf/modulo-strength-4/ ,
so basically we have to find all such pairs of no. (say i,j) such that A[i]%k=A[j]%k where k is a no. given in the question ,
i tried brute force approach and got time limit exceeded at some of the last test cases and
in the discussion tab i found a code which is working but i couldn't understand what exactly it does, and the underlying thinking behind the algorithm used.

#include <bits/stdc++.h>

using namespace std;
#define int long long
int32_t main() {
    int n,k,s=0;
    cin>>n>>k;
    int a[n];
    vector<int>v(k,0);  // Specially this part ,what does it store?
    for(int i=0;i<n;i++)
    {   
        cin>>a[i];
        v[a[i]%k]++;   
    }
    for(int i=0;i<k;i++)
    {
        s+=v[i]*(v[i]-1);
    }
    cout<<s;
}

Here is the code, i wanted to understand it so that i can apply this logic over other problems.

Answer 1

There are a few problems with that;

• "bits/stdc++.h" is not a standard header
• Variable-length arrays, like int a[n], are non-standard and prone to runtime errors (this one is also completely unnecessary)
• #define int long long makes the code have undefined behaviour.

Here is a fixed version, with some minor renaming and clarifying comments:

#include <iostream>
#include <vector>

int main() {
    long long n, k;
    cin >> n >> k;

    // There are k groups of friends.  
    std::vector<int> friends(k);
    // Count how many people there are in each group.  
    for(int i = 0; i < n; i++)
    {   
        int x;
        std::cin >> x;
        friends[x%k]++;   
    }
    long long sum = 0;
    for(int i = 0; i < k; i++)
    {
        // In a group of N mutual friends, each person has N-1 friends. 
        sum += friends[i] * (friends[i]-1);
    }
    std::cout << sum;
}

Answer 2

Let's first go through with the purpose of every variable in the code.

The purpose of n,k,s is explicitly given. a[n] is for reading the numbers in array. std::vector<int>v(k,0) stores k sized vector of 0's, and v[i] indicates the number of variables in a[n] for which a[j]%k==i.

In the last loop, the following has done. The number of pairs that can be constructed with n elements is n*(n-1) (basic combinatorics), and if we have v[i] numbers for which the condition is satisfied and a[j]%k==i the number of pairs that can be constructed is v[i]*(v[i]-1). The loop sums up the number of pairs for every remnant i.