Finding duplicates in O(n)

Input: Given an array of n elements which contains elements from 0 to n-1, with any of these numbers appearing any number of times.

Goal : To find these repeating numbers in O(n) and using only constant memory space.

#include <iostream>
using namespace std;
void duplicates(int a[], int n)
{
    for (int i = 0; i < n; i++)
    {
        while(a[a[i]]!=a[i])
            swap(a[a[i]],a[i]);
    }
    for (int i = 0; i < n; i++)
        if (a[i] != i)
            cout<<a[i]<<" ";
}
int main()
{
    int x[] = {1, 2, 3, 1, 3, 0, 6};
    int n = sizeof x / sizeof x[0];
    duplicates(x, n);
    return 0;
}

Shortest distance between 2 Integers

#include <iostream>
#include <climits>
using namespace std;
int dist(int a[],int n, int x, int y)
{
    int a1=-1,a2=-1, min_distance = INT_MAX;
    for(int i=0;i<n;i++)
    {
        if(a[i]==x)
        {
            a1 = i;
            int distance = a1-a2;
            if(a2>=0 && distance<min_distance)
            {
                min_distance = distance;
            }
        }
        else if(a[i]==y)
        {
            a2 = i;
            int distance = a2-a1;
            if(a1>=0 && distance<min_distance)
            {
                min_distance = distance;
            }
        }
    }
    return min_distance;
}
int main()
{
    int a[] = {6,5,5,5,1,2,4,4,6,6,3,4,3,4,1,2,4};
    int size= sizeof(a)/sizeof(a[0]);
    cout<<dist(a,size,1,6);
    return 0;
}

Count the number of occurrences in a sorted array

Algorithm

1. Use Binary search to get index of the first occurrence of x in arr[] (i)
2. Use Binary search to get index of the last occurrence of x in arr[] (j)
3. Return (j – i + 1)

#include <iostream>
using namespace std;
int lower_bound(int a[],int low,int high, int x)
{
    if(low<=high)
    {
        int mid = (low+high)/2;
        if(a[mid]==x && (a[mid-1]<x || mid==0)) return mid;
        if(x<a[mid])
            return lower_bound(a,low,mid-1,x);
        else
            return lower_bound(a,mid+1,high,x);
    }
    return -1;
}
int upper_bound(int a[],int low,int high, int x, int n)
{
    if(low<=high)
    {
        int mid = (low+high)/2;
        if(a[mid]==x && (a[mid+1]>x || mid==n-1)) return mid;
        if(x<a[mid])
            return upper_bound(a,low,mid-1,x,n);
        else
            return upper_bound(a,mid+1,high,x,n);
    }
    return -1;
}
int count(int a[],int n,int x)
{
    int i = lower_bound(a,0,n-1,x);
    if(i==-1) return 0;
    int j = upper_bound(a,0,n-1,x,n-1);
    return j-i+1;
}
int main()
{
    int a[] = {1,1,1,40,40,40,110};
    int n = sizeof(a)/sizeof(a[0]);
    cout<<count(a,n,40)<<endl;
    return 0;
}

Median of 2 sorted arrays of equal lengths

#include <iostream>
using namespace std;
int median(int a[],int n)
{
    if(n%2==0)
    {
        return (a[n/2]+a[n/2-1])/2;
    }
    else
    {
        return a[n/2];
    }
}
int getMedian(int a[],int b[],int n)
{
    if(n==0)
    {
        return 0;
    }
    else if(n==1)
    {
        return (a[0]+b[0])/2;
    }
    else if(n==2)
    {
        return (max(a[0],b[0])+min(a[1],b[1]))/2;
    }
    int m1 = median(a,n);
    int m2 = median(b,n);
    if(m1==m2)
    {
        return m1;
    }
    else if(m1<m2)
    {
        return getMedian(a+n/2,b,n-n/2);
    }
    else
    {
        return getMedian(a,b+n/2,n-n/2);
    }
}
int main()
{
    int ar1[] = {1, 12, 15, 26, 38};
    int ar2[] = {2, 13, 17, 30, 45};
    cout<<getMedian(ar1, ar2, 5);
    return 0;
}