The entry gate of the Orion Tower office building records every badge swipe of the day. By closing time the system has logged $N$ scans, where the $i$-th scan stored the numeric badge id $A_i$ of whoever walked through the gate. The security team knows one thing for certain about today's log: a single badge id was swiped **strictly more than** $\lfloor N/2 \rfloor$ times - some employee kept popping in and out all day. They call that id the **dominant badge**, and it is **guaranteed to exist** in the log. Your task is to inspect the scan log and report the dominant badge id. ### Function Description Complete the function `dominantBadge` provided in the editor. The function receives the following parameters: | Parameter | Type | Description | |---|---|---| | $N$ | integer | the number of badge scans recorded | | $A$ | array of integers | the badge ids in scan order, where $A_i$ is the id of the $i$-th scan | The function must return a single integer: the badge id that appears strictly more than $\lfloor N/2 \rfloor$ times in $A$. ### Input Format - The first line contains a single integer $N$ - the number of scans. - The second line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$ - the badge ids. ### Output Format Return a single integer: the dominant badge id. ### Notes - A dominant badge (one appearing strictly more than $\lfloor N/2 \rfloor$ times) is **always guaranteed** to exist, so the answer is unique. - Badge ids are not necessarily consecutive or small - they can be as large as $10^9$. - The scans appear in arbitrary order; the dominant id may be clustered together or scattered across the whole log.

Interview Questions/Coding/Dominant Badge Holder

Dominant Badge Holder

Preview mode. Log in to edit, run, submit, and save progress.

Easy

Dominant Badge Holder

The entry gate of the Orion Tower office building records every badge swipe of the day. By closing time the system has logged $N$ scans, where the $i$-th scan stored the numeric badge id $A_i$ of whoever walked through the gate. The security team knows one thing for certain about today's log: a single badge id was swiped strictly more than $\lfloor N/2 \rfloor$ times - some employee kept popping in and out all day. They call that id the dominant badge, and it is guaranteed to exist in the log. Your task is to inspect the scan log and report the dominant badge id. ### Function Description Complete the function `dominantBadge` provided in the editor. The function receives the following parameters:

Parameter	Type	Description
$N$	integer	the number of badge scans recorded
$A$	array of integers	the badge ids in scan order, where $A_i$ is the id of the $i$-th scan

The function must return a single integer: the badge id that appears strictly more than $\lfloor N/2 \rfloor$ times in $A$. ### Input Format - The first line contains a single integer $N$ - the number of scans. - The second line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$ - the badge ids. ### Output Format Return a single integer: the dominant badge id. ### Notes - A dominant badge (one appearing strictly more than $\lfloor N/2 \rfloor$ times) is always guaranteed to exist, so the answer is unique. - Badge ids are not necessarily consecutive or small - they can be as large as $10^9$. - The scans appear in arbitrary order; the dominant id may be clustered together or scattered across the whole log.

Examples

Example 1

Input:

```text
7
4 9 4 4 2 4 9
```

Output:

```text

Explanation: There are $N = 7$ scans, so a dominant badge must appear strictly more than $\lfloor 7/2 \rfloor = 3$ times. Badge $4$ appears $4$ times (positions $1, 3, 4, 6$), badge $9$ appears twice, and badge $2$ appears once. Since $4 > 3$, badge $4$ is the dominant badge.

Approach hint

A badge that appears more than $\lfloor N/2 \rfloor$ times occurs more often than all other badges combined. What happens if every occurrence of it cancels out one occurrence of a different badge?

Common mistake

Skipping assumptions, edge cases, or trade-offs can make an otherwise good answer feel incomplete.

Input

```text
7
4 9 4 4 2 4 9
```

Output

```text