×

# KOL16J - Editorial

Editorialist: Soumik Sarkar

CAKEWALK

Arrays, Sorting

# PROBLEM:

Given a list of $N$ integers, determine if all numbers from $1$ to $N$ appear exactly once, and whether the list is sorted.

# EXPLANATION:

A Tarantino movie must have two properties:
1. Each chapter from $1$ to $N$ must be in the movie
2. The chapters must not be in sorted order
If both properties are satisfied, the output is "yes", otherwise "no".

For the first condition, this easiest approach is to check whether each number from $1$ to $N$ appear in the array.

for i in [1..N]
flag = 0
for j in [1..N]
if i == A[j]
flag = 1
break current loop
if flag == 0
break current loop
if flag == 0
definitely not a Tarantino movie
else
proceed to check next condition

This algorithm has complexity $\mathcal{O}(N^2)$. This works just fine with the given constraints, but alternately one can generate a frequency array which would be $\mathcal{O}(N)$.

If the first check is passed, we know that the array only contains elements from $1$ to $N$. Now to check whether the array is sorted, we can just check whether each $A[i]$ is $A[i-1] + 1$ since this property holds true only when the array is sorted.

flag = 0
for i in [2..N]
if A[i] != A[i-1] + 1
flag = 1
break current loop
if flag == 0
cannot be a Tarantino movie
else
both tests have been passed!
This approach is $\mathcal{O}(N)$. Alternately, it is possible to sort a copy of $A$ and if $A$ is initially sorted the copy will be element-wise equal to $A$. This approach would be $\mathcal{O}(N^2)$ or $\mathcal{O}(N \log N)$ depending on the sorting procedure.

Overall complexity may be $\mathcal{O}(N)$, $\mathcal{O}(N^2)$ or $\mathcal{O}(N \log N)$.

# EDITORIALIST'S SOLUTION:

Editorialist's solution can be found here.
Editorialist's alternate solution can be found here.

6★meooow ♦
6.7k717
accept rate: 48%

19.5k348496535

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,026
×1,529
×743
×100
×6

question asked: 30 Oct '17, 18:48

question was seen: 504 times

last updated: 14 Nov '17, 00:00