anupomkar's blog

By anupomkar, history, 2 years ago, In English

Given a binary array, find the total number of subarrays with the ratio of 0's and 1's equal to x:y.

Constraints:

n = arr.length

2<=n<=1e5

1<=x,y<=n

Example: arr = [0,1,0,1] x = 1 y = 1

Output: 4

Explanation: The four possible subarrays are as follows:

[0 1] 0 1 --> [0,1]

0 [1 0] 1 --> [1,0]

0 1 [0 1] --> [0,1]

[0 1 0 1] --> [0,1,0,1]

With the given constraints, expecting solution no worse than O(n)

P.s: Maybe the problem can be solved using the sliding window technique. But unable to apply it due to ratio constraint.

Full text and comments »

  • Vote: I like it
  • +8
  • Vote: I do not like it

By anupomkar, history, 2 years ago, In English

Given a permutation array P (1-based indexing), find the total number of steps required to sort the same array using the permutation array.

Constraints: n = arr.length 2<=n<=10^5

Example: Say P =[2,5,4,3,1]

Copy the array from P to arr arr = [2,5,4,3,1] step1 -> arr = [5,1,3,4,2] {Here the elements are arranged according to the permutation array, (i.e, permutation array P is considered here as index array to arrange elements) Here, 2nd element (5) comes 1st place because in P, 2 is at 1st position 5th element (1) comes 2nd place because in P, 5 is at 2nd position and so on...}

step2 -> arr = [1,2,4,3,5] step3 -> arr = [2,5,4,3,1] step4 -> arr = [5,1,4,3,2] step5 -> arr = [1,2,3,4,5]

Hence, the total number of steps required = 5

Expecting O(n) solution according to given constraints.

Full text and comments »

  • Vote: I like it
  • +4
  • Vote: I do not like it