Wednesday 24 August 2011

Find the repeating and the missing in 1..n array of size n


/**
*
*/

package com.test.p2;

/**
*
@author Thejas
*Find the repeating and the missing
*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.
*
* Examples:
*arr[] = {3, 1, 3}
*Output: 2, 3 // 2 is missing and 3 occurs twice
*arr[] = {4, 3, 6, 2, 1, 1}
*Output: 1, 5 // 5 is missing and 1 occurs twice
*
******************************************************************************************
*Solution:
*Traverse array from 0th index, take the value at the current index in the array as the index and
*negate the value at this new index.While Traversing check if the value of the value of current index is -ve,
*if yes we have got the Repeated element at array of current index.
*
*Now traverse the same array and break when you find a positive value in the array for current index.
*current index+1 is ur missing element
******************************************************************************************/

public class FindRepeatingMissing {

/**
*
@param args
*/

public static void main(String[] args) {
// TODO Auto-generated method stub

int array[]={5,3,7,2,4,1,5};
int n=array.length;
int i=0,missing=0,repeat=0;
for(;i<n;i++)
{
if(array[(Math.abs(array[i]))-1] > 0)
{
array[(Math.abs(array[i]))-1] = array[(Math.abs(array[i]))-1]*(-1);
}else{
repeat=Math.abs(array[i]);
}
}
i=0;
for(;i<n;i++)
{
if(array[i]> 0)
{
missing=i+1;
}
}

System.out.println("The Missing ="+missing+" and Repeated ="+repeat+" !!");
return;
}

}

No comments:

Post a Comment