Xander Budnick is a famous you tuber. Currently he is in a mission to visit several
tourist spots and stay distinct number of days in each spot. So while he is visiting a
particular spot, he is a problem to find out the number of days he should stay in that
spot. You are given a sorted non-negative distinct integers, your task is to design an
algorithm that finds the smallest missing non-negative element on it. Your solution
should not takes more than logn instructions in worst case. Consider following
examples for better understanding.
Example:
Input: nums[] = [1, 2, 3, 4, 6, 9, 11, 15]
Output: The smallest missing element is 0
Input: nums[] = [0, 1, 2, 3, 4, 5, 6]
Output: The smallest missing element is 7
Code:
#include<stdio.h>
int findFirstMissing(int arry[],int start, int end){
if(start>end){
return end+1;
}
if(start !=arry[start]){
return start;
}
int mid = (start+end)/2;
if(arry[mid]==mid){
return findFirstMissing(arry,mid+1,end);
return findFirstMissing(arry,start,end);
}
}
int main(){
int arr[20];
int n;
printf("enter how many element:");
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&arr[i]);
}
printf("the smallst missing element: %d",findFirstMissing(arr,0,n-1));
return 0;
}
Run:
