HackerRank Combinatorics – Consecutive Subsequences

Challenge: Consecutive Subsequences

Subdomeniu: Combinatorics (combinatorics)

Scor cont: 50.0 / 50

Submission status: Accepted

Submission score: 1.0

Submission ID: 464734580

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/consecutive-subsequences/problem

Cerinta

Jigar got a sequence of __n__ positive integers as his birthday present! He likes consecutive subsequences whose sum is divisible by __k__. He asks you to write a program to count them for him.

__Input Format__ <br>
The first line contains **T**, the number of testcases.  
__T__ testcases follow. Each testcase consists of 2 lines.  
The first line contains **n** and **k** separated by a single space.  
And the second line contains __n__ space separated integers.

__Output Format__ <br>
For each test case, output the number of consecutive subsequenences whose sum is divisible by __k__ in a newline.

__Constraints__ <br>
1 ≤ T ≤ 20 <br>
1 ≤ n ≤ 10<sup>6</sup> <br>
1 ≤ k ≤ 100 <br>
1 ≤ a[i] ≤ 10<sup>4</sup> <br>

__Sample Input__
<pre>
2
5 3
1 2 3 4 1
6 2
1 2 1 2 1 2
</pre>

__Sample Output__
<pre>
4
9
</pre>

__Explanation__

For 

    1 2 3 4 1

there exists, 4 subsequences whose sum is divisible by 3, they are   

    3
    1 2
    1 2 3
    2 3 4

For 

    1 2 1 2 1 2

there exists, 9 subsequences whose sum is divisible by 2, they are  

    2
    2
    2
    1 2 1
    1 2 1
    1 2 1 2
    2 1 2 1
    1 2 1 2
    2 1 2 1 2

Cod sursa

//consecutive-subsequences.cpp
//Consecutive Subsequences
//Weekly Challenges - Week 6
//Author: derekhh

#include<iostream>
#include<cstring>
using namespace std;

int cnt[100];

int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		memset(cnt, 0, sizeof(cnt));
		int n, k, num, sum = 0;
		cin >> n >> k;
		cnt[0] = 1;
		for (int i = 0; i < n; i++)
		{
			cin >> num;
			sum += num;
			if (sum >= k) sum %= k;
			cnt[sum]++;
		}
		long long ret = 0;
		for (int i = 0; i < k; i++)
			ret += (long long)cnt[i] * (cnt[i] - 1) / 2;
		cout << ret << endl;
	}
	return 0;
}