Find minimum possible size of array with given rules for removing elements - GeeksforGeeks

Find minimum possible size of array with given rules for removing elements - GeeksforGeeks
Given an array of numbers and a constant k, minimize size of array with following rules for removing elements.

• Exactly three elements can be removed at one go.
• The removed three elements must be adjacent in array, i.e., arr[i], arr[i+1], arr[i+2]. And the second element must be k greater than first and third element must be k greater than second, i.e., arr[i+1] – arr[i] = k and arr[i+2]-arr[i+1] = k.

For every element arr[i] there are two possibilities
1) Either the element is not removed.
2) OR element is removed (if it follows rules of removal). When an element is removed, there are again two possibilities.
…..a) It may be removed directly, i.e., initial arr[i+1] is arr[i]+k and arr[i+2] is arr[i] + 2*k.
…..b) There exist x and y such that arr[x] – arr[i] = k, arr[y] – arr[x] = k, and subarrays “arr[i+1…x-1]” & “arr[x+1…y-1]” can be completely removed.

// dp[i][j] denotes the minimum number of elements left in

// the subarray arr[i..j].

int dp[MAX][MAX];

 

int minSizeRec(int arr[], int low, int high, int k)

{

    // If already evaluated

    if (dp[low][high] != -1)

        return dp[low][high];

 

    // If size of array is less than 3

    if ( (high-low + 1) < 3)

        return high-low +1;

 

    // Initialize result as the case when first element is

    // separated (not removed using given rules)

    int res = 1 + minSizeRec(arr, low+1, high, k);

 

    // Now consider all cases when first element forms a triplet

    // and removed. Check for all possible triplets (low, i, j)

    for (int i = low+1; i<=high-1; i++)

    {

        for (int j = i+1; j <= high; j++ )

        {

            // Check if this triplet follows the given rules of

            // removal. And elements between 'low' and 'i' , and

            //  between 'i' and 'j' can be recursively removed.

            if (arr[i] == (arr[low] + k) &&

                arr[j] == (arr[low] + 2*k) &&

                minSizeRec(arr, low+1, i-1, k) == 0 &&

                minSizeRec(arr, i+1, j-1, k) == 0)

            {

                 res = min(res, minSizeRec(arr, j+1, high, k));

            }

        }

    }

 

    // Insert value in table and return result

    return (dp[low][high] = res);

}

 

// This function mainlu initializes dp table and calls

// recursive function minSizeRec

int minSize(int arr[], int n, int k)

{

    memset(dp, -1, sizeof(dp));

    return minSizeRec(arr, 0, n-1, k);

}

Read full article from Find minimum possible size of array with given rules for removing elements - GeeksforGeeks