Best Solution in O(n) without data structure Overhead: Lang: Java

import java.io.IOException;

public class Main{ public static void main(String[] args) throws IOException { Reader reader = new Reader(); int n = reader.readInt(); int k = reader.readInt(); int ret = 0; int[] remainders = new int[k];

    //O(n)
    for (int i = 0; i < n; i++) {
        int rIndex = reader.readInt() % k;
        //Special Case
        if(rIndex == 0) {
            ret += remainders[0];
        }
        //Where k is even
        else if (rIndex == k - rIndex) {
            ret += remainders[k / 2];
        }

        //general case
        else {
            ret += remainders[k - rIndex];
        }

        remainders[rIndex]++;
    }

    System.out.println(ret);
}

}