C Program To Find Largest Interval of Integers For Which All Numbers In It Are Present In Given Array

This is a question asked in technical interview or programming round by the IT company Zoho during its recruitment process. The question is:

Write a program to find the largest interval (of integers) such that all the integers in the interval are present in the given array.

The input to the program is an integer array. The output is an integer interval (two integers as lower bound and upper bound of interval). All the elements in between the bounds (including the bounds) should be present in the array. Also, it should not be possible to find any other larger interval with all the numbers in it present in the array.

We first sort the given array in ascending order. Let

tlb= lower bound of temporary interval (interval in consideration)
tub= upper bound of temporary interval
upper_bound=upper bound of largest interval
lower_bound=lower bound of largest interval

We copy first element (a[0]) to all above variables. Then traverse the array from second element (a[1]) to its end. If the current element is equal to the previous element plus one, then the temporary upper bound (tub) is set to the current element. Otherwise, if (tub-tlb)>(upper_bound-lower_bound), temporary bounds are copied to the largest bounds and tlb and tub are set to current element.

The program is as follows:

#include<stdio.h>

void main()
{
int i,j,t,a[20],n,lower_bound,upper_bound,tlb,tub;
printf("\nEnter number of elements:");
scanf("%d",&n);
printf("\nEnter elements:");
for(i=0;i<n;i++)
    scanf("%d",&a[i]);
for(i=0;i<n-1;i++)
    {
    for(j=0;j<n-i-1;j++)
        {
        if(a[j]>a[j+1])
            {
            t=a[j];
            a[j]=a[j+1];
            a[j+1]=t;
            }
        }
    }
lower_bound=upper_bound=tlb=tub=a[0];
for(i=1;i<n;i++)
    {
    if(a[i]==a[i-1]+1)
        {
            tub=a[i];
        }
    else
        {
        if(tub-tlb>upper_bound-lower_bound)
            {
            upper_bound=tub;
            lower_bound=tlb;
            }
        tlb=a[i];
        tub=a[i];
        }
    }
if(tub-tlb>upper_bound-lower_bound)
            {
            upper_bound=tub;
            lower_bound=tlb;
            }
printf("\nLargest interval with all its elements present in array:[%d,%d]",lower_bound,upper_bound);
}