QUESTION
You are given an unsorted array with both positive and negative elements. You have to find the smallest positive number missing from the array in O(n) time using constant extra space.\n\nInput:\nFirst line consists of T test cases. First line of every test case consists of N, denoting the number of elements in array. Second line of every test case consists of elements in array.\n\nOutput:\nSingle line output, print the smallest positive number missing.\n\nConstraints:\n1<=T<=100\n1<=N<=100.
“TESTCASE_1”: “2\n5\n1 2 3 4 5\n5\n0 -10 1 3 -20\n###—###SEPERATOR—###—\n6\n2”, “TESTCASE_2”: “2\n5\n1 3 4 5 6\n5\n1 2 3 8 9\n###—###SEPERATOR—###—\n2\n4”, “TESTCASE_3”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_4”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0
ANSWER
/* Program to find the smallest positive missing number */
#include <stdio.h>
#include <stdlib.h>
/* Utility to swap to integers */
void swap(int *a, int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
/* Utility function that puts all non-positive (0 and negative) numbers on left
side of arr[] and return count of such numbers */
int segregate (int arr[], int size)
{
int j = 0, i;
for(i = 0; i < size; i++)
{
if (arr[i] <= 0)
{
swap(&arr[i], &arr[j]);
j++; // increment count of non-positive integers
}
}
return j;
}
/* Find the smallest positive missing number in an array that contains
all positive integers */
int findMissingPositive(int arr[], int size)
{
int i;
// Mark arr[i] as visited by making arr[arr[i] - 1] negative. Note that
// 1 is subtracted because index start from 0 and positive numbers start from 1
for(i = 0; i < size; i++)
{
if(abs(arr[i]) - 1 < size && arr[abs(arr[i]) - 1] > 0)
arr[abs(arr[i]) - 1] = -arr[abs(arr[i]) - 1];
}
// Return the first index value at which is positive
for(i = 0; i < size; i++)
if (arr[i] > 0)
return i+1; // 1 is added becuase indexes start from 0
return size+1;
}
/* Find the smallest positive missing number in an array that contains
both positive and negative integers */
int findMissing(int arr[], int size)
{
// First separate positive and negative numbers
int shift = segregate (arr, size);
// Shift the array and call findMissingPositive for
// positive part
return findMissingPositive(arr+shift, size-shift);
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int arr[20],arr_size,i;
scanf("%d",&arr_size);
for(i=0;i<arr_size;i++)
scanf("%d",&arr[i]);
int missing = findMissing(arr, arr_size);
printf("%d\n", missing);
}
getchar();
return 0;
}