Question

you are given an array of integers a and an integer k. your task is to calculate the number of ways to pick two different indices i < j, such that a[i] + a[j] is divisible by k.example:input: a = [1,2,3], k = 4 output: 3 explanation: pick indices i=0 and j=2. sum of elements at these indices is 1+3 = 4 (divisible by k). also pick index i=1 and j=2. sum of elements at these indices is 2+3 = 5 (divisible by k) . finally pick index i=0 and j=1. sum of elements at these indices is 1+2 = 3 (divisible by k). so total number of ways to select two different indices that add up to divisible by k in this array is 3 .*/

Answer 1

#include <iostream>

int count_pairs(int a[], int n, int k) {

int rem_count[k] = {0};

int count = 0;

for (int i = 0; i < n; i++) {

int rem = a[i] % k;

if (rem_count[k - rem] > 0) {

count += rem_count[k - rem];

}

rem_count[rem]++;

}

return count;

}

int main() {

int a[] = {1, 2, 3};

int n = sizeof(a) / sizeof(a[0]);

int k = 4;

std::cout << count_pairs(a, n, k) << std::endl;

return 0;

}

Step-by-step explanation:

This code defines the count_pairs() function to solve the problem, and calls it in the main() function with the given input. The sizeof() operator is used to get the size of the array a, and the result is divided by the size of the first element to get the number of elements in the array. The output of the function is printed to the console using std::cout.