Minimum operations required to remove an array

Revision en1, by wish_me, 2017-10-10 12:15:22

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English wish_me 2017-10-10 12:15:22 1018 Initial revision (published)