class Solution { //Function that puts all non-positive (0 and negative) numbers on left //side of arr[] and return count of such numbers. static int segregate (int arr[], int size) { int j = 0, i; for(i = 0; i < size; i++) { if (arr[i] <= 0) { int temp; //changing the position of negative numbers and 0. temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; //incrementing count of non-positive integers. j++; } } return j; } //Finding the smallest positive missing number in an array //that contains only positive integers. static int findMissingPositive(int arr[], int size) { int i; //marking arr[i] as visited by making arr[arr[i] - 1] negative. //note that 1 is subtracted because indexing starts from 0 and //positive numbers start from 1. for(i = 0; i < size; i++) { if(Math.abs(arr[i]) - 1 < size && arr[Math.abs(arr[i]) - 1] > 0) arr[Math.abs(arr[i]) - 1] = -arr[Math.abs(arr[i]) - 1]; } for(i = 0; i < size; i++) { if (arr[i] > 0) { //returning the first index where value is positive. // 1 is added because indexing starts from 0. return i+1; } } return size+1; } //Function to find the smallest positive number missing from the array. static int missingNumber(int arr[], int size) { //first separating positive and negative numbers. int shift = segregate (arr, size); int arr2[] = new int[size-shift]; int j=0; //shifting the array to access only positive part. for(int i=shift;i<(size);i++) { arr2[j] = arr[i]; j++; } //calling function to find result and returning it. return findMissingPositive(arr2, j); } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter