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: 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[i1] + 1$ since this property holds true only when the array is sorted. flag = 0 for i in [2..N] if A[i] != A[i1] + 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 elementwise 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. asked 30 Oct '17, 18:48
