You are given a list of length n+1 with a range of numbers from 1 to n where one of the numbers is repeated, you have to find the repeated number. This question is very similar to the find the missing number in an array. In this post, I will be sharing a java program and algorithm to find out a duplicate number between 1 to n numbers.

Read Also: Find the missing number in an Array in Java

Algorithm

1. Calculate the sum of all the numbers in the list.
2. Calculate size n of unique numbers in the list and use arithmetic progression formula n*(n+1)/2
3. Subtract the value obtained in step 2 from step 1. You will get the duplicate number.

Java Program

 import java.util.List;
import java.util.ArrayList;
public class DuplicateNumberProgram {
    public static void main(String args[]) {
        // Creating the list 
        List<Integer> numbers = new ArrayList<Integer>();
        // Add numbers from 1 to n
        for(int i=1; i < 40; i++) {
            numbers.add(i);
        }
        // adding duplicate number into the list
        numbers.add(35);
        DuplicateNumberProgram obj = new DuplicateNumberProgram();
        int duplicateNumber = obj.getDuplicateNumber(numbers);
        System.out.println(duplicateNumber);
    }
    
    public int findSum(List<Integer> numbers) {
        int sum =0;
        for(int number : numbers) {
            sum += number;
        }
        return sum;
    }
    
    public int getDuplicateNumber(List<Integer> numbers) {
        int n = numbers.size()-1;
        int total = findSum(numbers);
        int duplicateNum = total - (n * (n+1)/2);
        return duplicateNum;
    }
}

Output:

35


That's all for today, please mention in the comments in case you have any questions related to the find out a duplicate number between 1 to n numbers in Java.