Problem Statement
A majority element of an array A is an element that occurs in A strictly more than length(A)/2 times. In other words, the number of occurrences of the majority element must be strictly larger than the number of occurrences of all other elements combined. For example, the majority element of the array {1, 2, 1} is 1. On the other hand, the arrays {1, 2, 3} and {1, 2, 1, 3} don't have any majority element.
You are given a
You are given the
for i = 0 .. n-1:
A[i] = (seed div 2^16) modulo m
seed = (seed * 1103515245 + 12345) modulo 2^31
In the pseudocode shown above, ^ denotes exponentiation and div denotes integer division (e.g., 49 div 10 is 4).
Definition
- Class:
- MajoritySubarray
- Method:
- getCount
- Parameters:
- int, int, int
- Returns:
- long
- Method signature:
- long getCount(int n, int seed, int m)
- (be sure your method is public)
Notes
- The reference solution does not depend on any properties of the pseudorandom generator used in the statement. In the given time limit the reference solution can compute the answer for any array of length 10^5.
- Watch out for integer overflow. In particular, note that the return value may not fit into a signed 32-bit integer variable.
Constraints
- n will be between 1 and 105, inclusive.
- seed will be between 0 and 231-1, inclusive.
- m will be between 1 and 50, inclusive.
Examples
5
200
5
Returns: 8
For these arguments you should generate the array A = {0, 0, 1, 2, 0}. During the generation, the variable seed should have the following values: {200, 1659729249, 1659156614, 155161927, 1266180468, 598410909}. This array has exactly 8 contiguous subarrays that have a majority element, namely: Each of the five one-element subarrays. (Note that three of these look the same, but we are still counting each of them as a different subarray.) The subarray {0, 0}. The subarray {0, 0, 1}. The subarray {0, 0, 1, 2, 0}.
10
15
3
Returns: 23
The corresponding array is A = {0, 2, 2, 0, 0, 1, 1, 0, 2, 2}.
100000
345
2
Returns: 4984459804
100000
784
2
Returns: 4988932294
100000
0
1
Returns: 5000050000
100000
999
2
Returns: 4984429965
100000
2147483647
2
Returns: 4985531836
100000
14
3
Returns: 895638
100000
22
3
Returns: 912867
100000
6436342
3
Returns: 891248
100000
3342
3
Returns: 910949
100000
123213
50
Returns: 108534
100000
54534555
50
Returns: 108540
100000
1111
50
Returns: 108830
100000
0
50
Returns: 108576
4
12
6
Returns: 6
1
2
50
Returns: 1
2
213322
2
Returns: 3
8
12345678
1
Returns: 36
27
541
50
Returns: 27
The generated input is A = {0, 19, 46, 25, 21, 34, 29, 15, 24, 38, 22, 41, 17, 28, 37, 14, 4, 32, 11, 42, 2, 12, 44, 35, 39, 1, 10}.
10000
1
1
Returns: 50005000
100000
200
5
Returns: 278163
99999
12312
45
Returns: 109541
100000
123
1
Returns: 5000050000
100000
22
2
Returns: 4988635316
100000
1073741824
29
Returns: 115389
99999
541
50
Returns: 108139
100000
123
3
Returns: 896428
100000
0
2
Returns: 4988720471
9999
432425
50
Returns: 10782
100000
114
11
Returns: 149342