MajoritySubarray | Topcoder Archive

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 int[] A of length n. Each element of A is a small non-negative integer (between 0 and m-1, inclusive). Your task is to count the number of contiguous subarrays of A that have a majority element, and to return that count.

You are given the ints n, seed, and m. Since the array A may be long, it is not given explicitly. Instead, use the following pseudocode to generate its contents:

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}.
```
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}.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.