Algorithm Misc 3

http://www.geeksforgeeks.org/k-th-smallest-element-removing-integers-natural-numbers/

Given an array arr[] of size ‘n’ and a positive integer k. Consider series of natural numbers and remove arr[0], arr[1], arr[2], …, arr[p] from it. Now the task is to find k-th smallest number in the remaining set of natural numbers. If no such number exists print “-1”.

Input : arr[] = {1, 3}, k = 4.
Output : 6
First 5 Natural number {1, 2, 3, 4, 5, 6,  .. }
After removing {1, 3}, we get {2, 4, 5, 6, ... }.

First, sort the array arr[]. Observe, there will be arr[0] – 1 numbers between 0 and arr[0], similarly, arr[1] – arr[0] – 1 numbers between arr[0] and arr[1] and so on. So, if k lies between arr[i] – arr[i+1] – 1, then return K-th smallest element in the range. Else reduce k by arr[i] – arr[i+1] – 1 i.e., k = k – (arr[i] – arr[i+1] – 1).

Algorithm to solve the problem:

1. Sort the array arr[].
2. For i = 1 to k. Find c = arr[i+1] - arr[i] -1.
  a) if k - c <= 0, return arr[i-1] + k.
  b) else k = k - c.

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

{

    sort(arr, arr+n);

 

    // Checking if k lies before 1st element

    if (k < arr[0])

        return k;

 

    // If k is the first element of array arr[].

    if (k == arr[0])

        return arr[0] + 1;

 

    // If k is more than last element

    if (k > arr[n-1])

        return k + n;

 

    // If first element of array is 1.

    if (arr[0] == 1)

        k--;

 

    // Reducing k by numbers before arr[0].

    else

        k -= (arr[0] - 1);

 

    // Finding k'th smallest element after removing

    // array elements.

    for (int i=1; i<n; i++)

    {

        // Finding count of element between i-th

        // and (i-1)-th element.

        int c = arr[i] - arr[i-1] - 1;

        if (k <= c)

            return arr[i-1] + k;

        else

            k -= c;

    }

 

    return arr[n-1] + k;

}

http://www.geeksforgeeks.org/check-whether-arithmetic-progression-can-formed-given-array/

Given an array of n integers. The task is to check whether an arithmetic progression can be formed using all the given elements. If possible print “Yes”, else print “No”.

Method 3(Use Hashing)

1. Find out the smallest and second smallest elements
2. Find different between the two elements. d = second_smallest – smallest
3. Store all elements in a hashmap and return “NO” if duplicate element found (can be done together with step 1).
4. Now start from “second smallest element + d” and one by one check n-2 terms of Arithmetic Progression in hashmap. If any value of progression is missing, return false.
5. Return “YES” after end of the loop.

http://www.geeksforgeeks.org/check-exist-two-elements-array-whose-sum-equal-sum-rest-array/

We have an array of integers and we have to find two such elements in the array such that sum of these two elements is equal to the sum of rest of elements in array.

bool checkPair(int arr[],int n)

{

    // Find sum of whole array

    int sum = 0;

    for (int i=0; i<n; i++)

        sum += arr[i];

    // If sum of array is not even than we can not

    // divide it into two part

    if (sum%2 != 0)

        return false;

    sum = sum/2;

    // For each element arr[i], see if there is

    // another element with vaalue sum - arr[i]

    unordered_set<int> s;

    for (int i=0; i<n; i++)

    {

        int val = sum-arr[i];

        // If element exist than return the pair

        if (s.find(val) != s.end())

        {

            printf("Pair elements are %d and %d\n",

                                    arr[i], val);

            return true;

        }

        s.insert(arr[i]);

    }

    return false;

}




http://www.geeksforgeeks.org/size-array-repeated-deletion-lis/

Given an array arr[0..n-1] of positive element. The task is to print remaining elements of arr[] after repeated deletion of LIS (of size greater than 1). If there are multiple LIS with same length, we need to choose the LIS that ends first.

We repeatedly find LIS and remove its elements from array.

vector<int> findLIS(vector<int> arr, int n)

{

    // L[i] - The Maximum Sum Increasing

    // Subsequence that ends with arr[i]

    vector <vector<int> > L(n);

    // L[0] is equal to arr[0]

    L[0].push_back(arr[0]);

    // start from index 1

    for (int i = 1; i < n; i++)

    {

        // for every j less than i

        for (int j = 0; j < i; j++)

        {

            /* L[i] = {MaxSum(L[j])} + arr[i]

            where j < i and arr[j] < arr[i] */

            if (arr[i] > arr[j])

                L[i] = L[j];

        }

        // L[i] ends with arr[i]

        L[i].push_back(arr[i]);

    }

    // set lis =  LIS

    // whose size is max among all

    int maxSize = 1;

    vector<int> lis;

    for (vector<int> x : L)

    {

        // The > sign makes sure that the LIS

        // ending first is chose.   

        if (x.size() > maxSize)

        {

            lis = x;

            maxSize = x.size();

        }

    }

    return lis;

}

// Function to minimize array

void minimize(int input[], int n)

{

    vector<int> arr(input, input + n);

    while (arr.size())

    {

        // Find LIS of current array

        vector<int> lis = findLIS(arr, arr.size());

        // If all elements are in decreasing order

        if (lis.size() < 2)

            break;

        // Remove lis elements from current array. Note

        // that both lis[] and arr[] are sorted in

        // increasing order.

        for (int i=0; i<arr.size() && lis.size()>0; i++)

        {

            // If first element of lis[] is found

            if (arr[i] == lis[0])

            {

                // Remove lis element from arr[]

                arr.erase(arr.begin()+i) ;

                i--;

                // Erase first element of lis[]

                lis.erase(lis.begin()) ;

            }

        }

    }

    // print remaining element of array

    int i;

    for (i=0; i < arr.size(); i++)

        cout  << arr[i] << " ";

    // print -1 for empty array

    if (i == 0)

        cout << "-1";

}