Java-Programs/First_Missing_Positive_Number.java at master · codeankit10/Java-Programs · GitHub

History

53 lines (40 loc) · 1.13 KB

Raw

import java.util.Arrays;

import java.util.Scanner;

/*Given an unsorted integer array, find the smallest missing positive integer.

It should run in O(n) time and uses constant extra space.

Example 1:

Input: [1,2,0]

Output: 3 */

public class First_Missing_Positive_Number {

public static void main(String[] args) {

Scanner sc= new Scanner(System.in);

int N=sc.nextInt();

int []Arr= new int[N];

for( int i=0;i<N;i++)

Arr[i]=sc.nextInt();

System.out.println(firstMissingPositive(Arr));

}

static int firstMissingPositive(int[] nums) {

int n=nums.length;

int i=0;

while(i<n){

if(nums[i]>0&&nums[i]<=n&&nums[nums[i]-1]!=nums[i]){

swap(i,nums[i]-1,nums) ;

}

else

i++;

}

System.out.println(Arrays.toString(nums));

for( i=0;i<n;i++){

if(nums[i]!=i+1){

return i+1;

}

return n+1;

}

static void swap(int x,int y,int[]A){

int t=A[x];

A[x]=A[y];

A[y]=t;

}

Java-Programs/First_Missing_Positive_Number.java at master · codeankit10/Java-Programs · GitHub

Expand file tree

Breadcrumbs

First_Missing_Positive_Number.java

Latest commit

History

Breadcrumbs

First_Missing_Positive_Number.java

File metadata and controls