Hackerrank – Problem Statement
A description of the problem can be found on Hackerrank.
Solution
http://stackoverflow.com/questions/24518682/count-subsequences-divisible-by-k
I created solution in:
All solutions are also available on my GitHub profile.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
import java.util.Scanner; // http://stackoverflow.com/questions/24518682/count-subsequences-divisible-by-k public class ConsecutiveSubsequences { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int tests = scanner.nextInt(); for(int l = 0; l < tests; l++) { int n = scanner.nextInt(); int k = scanner.nextInt(); long[] numbers = new long[n]; for(int i = 0; i < n; i++) { numbers[i] = scanner.nextLong(); } long[] prefixModCount = new long[k]; for(int i = 0; i < k; i++) { prefixModCount[i] = 0; } prefixModCount[0] = 1; int prefixSum = 0; for(int i = 0; i < numbers.length; i++) { prefixSum += numbers[i]; prefixSum %= k; prefixModCount[prefixSum] += 1; } long result = 0; for(int mod = 0; mod < k; mod++) { result += prefixModCount[mod] * (prefixModCount[mod] - 1) / 2; } System.out.println(result); } scanner.close(); } } |