Majority Element

Majority Element

Medium Python Lists 20 views
Explanation Complexity

Problem Statement

Read n integers. If an element appears more than n/2 times, output it else output NONE.

Input Format

First line n. Second line n integers.

Output Format

Majority or NONE.

Example

7
2 2 1 2 3 2 2
2

Constraints

1

Input / Output Format

Input Format
First line n. Second line n integers.
Output Format
Majority or NONE.
Constraints
1

Examples

Input:
7 2 2 1 2 3 2 2
Output:
2

Example Solution (Public)

Python 
import sys
p=sys.stdin.read().strip().split()
if not p: sys.exit(0)
n=int(p[0])
a=list(map(int,p[1:1+n]))
cand=None
cnt=0
for v in a:
  if cnt==0:
    cand=v
    cnt=1
  elif v==cand:
    cnt+=1
  else:
    cnt-=1
if cand is None:
  sys.stdout.write('NONE')
else:
  c=0
  for v in a:
    if v==cand:
      c+=1
  sys.stdout.write(str(cand) if c>n//2 else 'NONE')

Official Solution Code

import sys
p=sys.stdin.read().strip().split()
if not p: sys.exit(0)
n=int(p[0])
a=list(map(int,p[1:1+n]))
cand=None
cnt=0
for v in a:
  if cnt==0:
    cand=v
    cnt=1
  elif v==cand:
    cnt+=1
  else:
    cnt-=1
if cand is None:
  sys.stdout.write('NONE')
else:
  c=0
  for v in a:
    if v==cand:
      c+=1
  sys.stdout.write(str(cand) if c>n//2 else 'NONE')
Please login to submit solutions.
Editor
Output

                                        

                                    

                                    

                                        

                                                                                    
Please login to submit solutions.