Monday, December 22, 2014

Java Program to find missing and repeated number from an unsorted array.

2:28 PM

Problem : Given an unsorted array of size n. Array elements are in range from 1 to n.One number from set {1, 2, …n} is missing and one number occurs twice in array. Find these two numbers.



Approach to solve (Algorithm)

1. Sort the input unsorted Array in ascending order.
2. Run a loop from index 0 to length-1;
2. Find the difference between element at i & i+1 index.
if difference==-1 continue the loop;
   else
if(difference==0) //So the Number at i index is repeated 
   else

if(difference==-2)//So the Number at index[i]+1 is missing. 



Solution:


/**
 * Created by DieHardTechy on 22-12-2014.
 */

import java.util.Arrays;

public class ArrayMissingDuplicate {

    public static void main(String[] arg) {
        //Unsorted Array which contains a duplicate number and a missing number
        int unsortedArr[] = {9, 8, 6, 6, 7, 4, 3, 1, 2};
        findMissingDuplicate(unsortedArr);
    }

    public static void findMissingDuplicate(int[] inputArr) {
        Arrays.sort(inputArr); //Sorts the input array in ascending order

        for (int i = 0; i < inputArr.length - 1; i++) {
            if (inputArr[i] - inputArr[i + 1] == -1) {
                continue;
            } else if (inputArr[i] - inputArr[i + 1] == 0) {
                System.out.println("Duplicate number is " + inputArr[i]);
            } else if (inputArr[i] - inputArr[i + 1] == -2) {
                System.out.println("Missing number is " + (inputArr[i] + 1));
            }
        }
    }

}

0 comments :

Post a Comment

 

© 2014 DieHardTechy . All rights resevered. Designed by Diehardtechy