v0rtex's blog

By v0rtex, history, 2 years ago, In English

We are given an array of integers 1 <= a[i] <= 20, of size N (1<= N <= 10 ^ 5) and we have to group similar elements together. In one operation we can swap two adjacent elements. Find the minimum no of swaps.

Input — 1 2 1 2 1 Output — 3

Input — 1 3 3 2 Output — 0

Input — 1 3 2 1 2 3 Output — 4

Explanation of test case 3 — swap a[2] with a[3] swap a[4] with a[3] swap a[4] with a[5] swap a[2] with a[3] The array becomes — { 1, 1, 2, 2, 3, 3}

Full text and comments »

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

By v0rtex, history, 2 years ago, In English

An array of size N is given and a value K. You have to find the minimum subset size so that subset sum is exactly equal to K, if not print -1. 0 < K, a[i], N < 10^6.

Full text and comments »

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

By v0rtex, history, 2 years ago, In English

If you are given an unsorted array of size N and some queries Q which consists of l,r as the range of the subarray. The task is to find the median of this subarray. 1<=N,Q<=5*10^4. Now if we sort the subarray per query the time complexity will be Q*nlogn (here n is the length of the subarray) which will give us TLE. Can anybody share the optimal approach?

Full text and comments »

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