Searching...
Thursday, 8 December 2016

How to find duplicate number between 1 to n th Numbers

21:02

Sample program and Algorithm

package com.vinod.test;


import java.util.ArrayList;
import java.util.List;


/**
 *@authorvinodkariyathungalkumaran
 *
 */
public class FindDuplicateNumber {


    public static void main(String a[]) {
        List<Integer> numbers = new ArrayList<Integer>();
        for (int i = 1; i <= 50; i++) {
            numbers.add(i);
        }
        numbers.add(11);
        FindDuplicateNumber duplicateNumber = new FindDuplicateNumber();
        System.out.println("Duplicate Number in the list: " + duplicateNumber.findDuplicateNumber(numbers));
    }

    /**
     * Algorithm to find out the duplicate number from 1 to n th value
     *
     *1)First find out the sum of the all values in the array list
     *
     *2)Find out the sum of the 1 to n th values 
     *
     *3) duplicate value = Frist step value- Second step value
     *
     *
     *@param numbers
     *@return
     */
    public int findDuplicateNumber(List<Integer> numbers) {
        int highestNumber = numbers.size() - 1;
        int sum = numbers.stream().mapToInt(Integer::intValue).sum();
        int duplicate = sum - (highestNumber * (highestNumber + 1) / 2);
        return duplicate;
    }


}

Output

Duplicate Number in the list: 11

 

 

0 comments: