Name123's blog

By Name123, history, 2 months ago, ,

Given an array A that is a permutation of n numbers [1-n]. Find the number of subarrarys S that meets the following condition max(S) — min(S) = length(S) — 1.

Example 1:

Input: [4, 3, 1, 2, 5] Output: 10 Explanation: subarrays that meets the condition are [4] [3] [1] [2] [5] [4 3] [1 2] [3 1 2] [4 3 1 2] [4 3 1 2 5]

There are 10 subarray that meets the condition, so the answer should be 10.

Is there a better than O(n^2) solution?

• -20

 » 2 months ago, # | ← Rev. 2 →   0 https://codeforces.com/blog/entry/70503?locale=enCan you please specify the source?
•  » » 2 months ago, # ^ |   0 Google Interview
 » 2 months ago, # |   0 This problem is being asked a record third time
 » 2 months ago, # | ← Rev. 3 →   0 you should for every number i from 1 to n calculate that: 0!+1!+2!+.....+(n-i)!;And then get sum of all this calculation.for every i you should store in an array D that:D[i] = 0!+1!+2!+....+i!how can you calculate an array D? d[0] = 1; for i from 1 to n: d[i] = d[i-1]*i;And then: for i from 1 to n: ans += D[n-i] print ans;
•  » » 2 months ago, # ^ |   0 How have you come up with this thing?