Showing posts with label Arrays Puzzle. Show all posts
Showing posts with label Arrays Puzzle. Show all posts

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;
}

}