int divisibleSumPairs(int n, int k, vector<int> ar) {
    int count = 0;
    
    for (int i = 0; i < n; ++i)
    {
        for(int j = i; j < n; ++j)
        {   
            if(j != i)
            {
                if(IsDivisiblyByK(ar[i] + ar[j], k))
                {
                    count++;
                }
            }
        }
    }
    return count;
}

function divisibleSumPairs(n, k, ar) {
    
    let sum=0,count=0,i,j;
    
    for(i=0; i<n; i++){
        for(j=i+1; j<n; j++){
            sum=ar[i]+ar[j];
            if(sum%k==0){
                count++;
            }
        }
    }
 return count;
}

sets=[]

for i in range(len(ar)):
    for j in range(len(ar)):
        if i<j:
            if (ar[i]+ar[j])%k==0:
                sets.append((ar[i],ar[j]))
return len(sets)

def divisible_sum_pairs(n: int, k: int, ar: list[int]):
    #Time complexity: O(n+k)
    #Space complexity (ignoring input): O(k)
    possible_remainders = {}
    total_pairs = 0

    for number in ar:
        remainder = number % k
        if remainder in possible_remainders:
            possible_remainders[remainder] += 1
        else:
            possible_remainders[remainder] = 1

    # For remainder 0 or k/2, the total pairs will be n choose 2
    if 0 in possible_remainders:
        total_pairs += int(possible_remainders[0] * (possible_remainders[0] - 1) / 2)
    k_is_pair = k % 2 == 0
    half_k = int(k / 2)
    if k_is_pair and (half_k in possible_remainders):
        total_pairs += int(
            possible_remainders[half_k] * (possible_remainders[half_k] - 1) / 2
        )

    # For the rest of the remainders, just need to multiply
    for remainder in range(1, int((k + 1) / 2)):
        if (remainder in possible_remainders) and (
            (k - remainder) in possible_remainders
        ):
            total_pairs += int(
                possible_remainders[remainder] * (possible_remainders[k - remainder])
            )

    return total_pairs

pub fn divisible_sum_pairs(n: i32, k: i32, ar: &[i32]) -> i32 {
    //Time complexity: O(n+k)
    //Space complexity (ignoring input): O(k)
    let mut remainder_dictionary = std::collections::HashMap::new();
    for number in ar {
        let remainder = number % k;
        match remainder_dictionary.get(&remainder) {
            Some(n) => remainder_dictionary.insert(remainder, n + 1),
            None => remainder_dictionary.insert(remainder, 1),
        };
    }

    let mut total_pairs = 0;
    //For remainders 0 and k/2, the total pairs will be n choose 2
    println!(
        "->> remainder_dictionary <<- function: divisible_sum_pairs; file: week1.rs\n{:?}",
        remainder_dictionary
    );
    total_pairs += match remainder_dictionary.get(&0) {
        Some(n) => n * (n - 1) / 2,
        None => 0,
    };
    let k_is_pair = k % 2 == 0;
    if k_is_pair {
        total_pairs += match remainder_dictionary.get(&(k / 2)) {
            Some(n) => n * (n - 1) / 2,
            None => 0,
        };
    }

    for remainder in 1..(k + 1) / 2 {
        total_pairs += remainder_dictionary.get(&remainder).unwrap_or(&0)
            * remainder_dictionary.get(&(k - remainder)).unwrap_or(&0);
    }

    total_pairs
}