In this article we are going to discuss a problem from arrays; this is one of the most commonly asked interview question of today.
 

Given an array of integers such that, it contains all the numbers from 1 to n in order but any of the number is repeated, find out that repeated element.

e.g. The input array of size 5 can have elements like {1,2,3,3,4} or {1,1,2,3,4}, so we have to find repeated element.

Here is a straight forward solution for the problem, we know that such kind of array element can be considered as a part of Arithmetic Series but having a repeated element. We have to find sum of element if there were no repeated element, and that the sum of current array. We can than identify the repeated element as shown in example below:
 

package com.tbNext.byexample;

public class TBArrayRepeatedElement {

	public static void main(String[] args) {
		int[] arr = { 1, 2, 3, 4, 5, 5 };
		TBArrayRepeatedElement arrayRepeatedElement = new TBArrayRepeatedElement();
		System.out.println("Repeated Element: "
				+ arrayRepeatedElement.repeatedElement(arr));
	}

	private int repeatedElement(int arr[]) {
		int rElement = -1;
		int aLength = arr.length;
		int lastElement = arr[aLength - 1];

		int expectedSum = (aLength * (aLength + 1)) / 2;
		int presentSum = arraySum(arr);

		rElement = (lastElement + 1) - (expectedSum - presentSum);

		return rElement;
	}

	private int arraySum(int arr[]) {
		int sum = 0;
		for (int i : arr)
			sum += i;
		return sum;
	}

}


Output

Repeated Element: 5

 


That's it, we have seen Find out duplicate number in an array, having n elements . In upcoming articles of Java Algorithms and interview series we will see more about Java and Related programming problems and solutions.

 

  • By Techburps.com
  • May 9, 2015
  • Programming