FACEBOOK - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: notsoloud
Testers: nishant403, satyam_343
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

Given the number of likes and comments on N posts, find out which one is most popular.

EXPLANATION:

This task is mostly an exercise in correctly and directly implementing what is asked for.
There are several ways to solve it, here’s one.

Let’s maintain the answer index, \text{ans}. Initialize \text{ans} to 1.

Now, for each i from 2 to N,

  • If A_i \gt A_\text{ans}, set \text{ans} = i because the i-th post has strictly more likes than the best so far; so it becomes the best so far.
  • If A_i \lt A_\text{ans}, the i-th post can never be the most popular, so we can ignore it.
  • Otherwise, we have A_i = A_\text{ans}.
    • In this case, compare B_i with B_\text{ans}. If B_i \gt B_\text{ans}, then set \text{ans} = i; otherwise don’t update \text{ans}.

Finally, print \text{ans}.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Code (Python) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    ans = 0
    for i in range(1, n):
        if a[i] > a[ans]: ans = i
        elif a[i] == a[ans] and b[i] > b[ans]: ans = i
    print(ans+1)
1 Like