PROBLEM LINK:
Editorialist: Soumik Sarkar
DIFFICULTY:
CAKEWALK
PREREQUISITES:
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:
- Each chapter from 1 to N must be in the movie
- 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.