wish_me's blog

Minimum operations required to remove an array
By wish_me, history, 7 years ago, In English

Minimum operations required to remove an array Given an array of N integers where N is even. There are two kinds of operations allowed on the array.

  1. Increase the value of any element A[i] by 1.
  2. If two adjacent elements in the array are consecutive prime number, delete both the element. That is, A[i] is a prime number and A[i+1] is the next prime number.

The task is to find the minimum number of operation required to remove all the element of the array.

size of array 10^5

size of element 10^3

Examples:

Input : arr[] = { 1, 2, 4, 3 } Output : 5

Minimum 5 operation are required.

  1. Increase the 2nd element by 1 { 1, 2, 4, 3 } -> { 1, 3, 4, 3 }

  2. Increase the 3rd element by 1 { 1, 3, 4, 3 } -> { 1, 3, 5, 3 }

  3. Delete the 2nd and 3rd element { 1, 3, 5, 3 } -> { 1, 3 }

  4. Increase the 1st element by 1 { 1, 3 } -> { 2, 3 }

  5. Delete the 1st and 2nd element { 2, 3 } -> { }

Input : arr[] = {10, 12} Output : 3

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

»
7 years ago, # |
  Vote: I like it +20 Vote: I do not like it

Can you provide a link to the problem? I only have an N^3 algorithm so far (at least it's polynomial :)) ).

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Is your algorithm (O(N^3)) 2-D dynamic programming? (considering that every any given pair which were removed together, let say number (a, b), resulting in greddy approach to find the nearest prime factors they were converted to).

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Yes, an right now, I'm thinking about how to solve the next particular problem (which is included in this one). If I give you an array of numbers between 1 and ~100 (the number of prime numbers <= 1000) with length of about 100.000, is there any way of matching positions so that each position is part of a match, no two matches intersect and each match i-j has a[j] = a[i] + 1 (basically a paranthesation with that property between the opening and the closing bracket). If you consider the array v[i] = a[i]th prime, then this is equivalent to asking whether the result to the initial problem applied for vector v is exactly N/2 or not. I'm still unable to solve this one...

      → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Isn't it just necessary to increase every Ai to the next prime? Then you can do N / 2 removals in any order. This could be done in linear time.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it +5 Vote: I do not like it

      It needs to be consecutive primes — (5, 7) is fine while (5, 13) is not.

      Edit: wrote (5, 8) instead of (5, 7).... why did I think fibonacci?

      → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Actually I got this problem in an interview. Can you explain your approach please?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Well you could easily compute for each pair (i, j) cost[i][j] = number of +1 operations you need to apply on ith and jth positions so that a[i] and a[j] become consecutive primes. Then you keep dp[i][j] = the minimum number of operations to remove the segment [i, j]. dp[i][j] = min (dp[i][k] + dp[k + 1][j]) for i <= k < j. Then you also have the possibility that dp[i][j] = cost[i][j] + dp[i + 1][j — 1]. That's all

      → Reply