find single repeating number from a big array

Carvia Tech | May 05, 2019 | 1 min read | 2 views | algorithm-datastructures


We have an array that contains large number of entries, all of them are unique except one that is repeating twice. We need to find that repeating number in a minimum time O(n) time and O(1) space complexity

Input: [1, 2, 2, 3, 4, 5, 6]
Output: 2

Sum of the Elements

We can sum up all the elements of input array and compare it with the below output:

\$1 + 2 + 3 + 4 + .. + n = (n * (n + 1)) / 2\$

The difference between actual array sum and math sum will give us the single duplicate number.

In Kotlin, we can write the below program to find the single duplicate number:

Kotlin: print single duplicate number
val array = arrayOf(1, 2, 3, 4, 5, 6, 7, 8, 9, 2)
val sum = array.sum()
val mathSum = ((array.size -1) * array.size) / 2
val duplicateNumber = sum - mathSum
println(duplicateNumber)
Program output

2


Top articles in this category:
  1. Citibank Java developer interview questions
  2. BlackRock Top Java Interview Questions: Investment Banking Domain
  3. Cracking core java interviews - question bank
  4. Morgan Stanley Java Interview Questions
  5. Top 50 Multi-threading Java Interview Questions for Investment Bank
  6. Top 20 Java Concurrency Interview Questions and Answers
  7. Sapient Global Market Java Interview Questions and Coding Exercise



Find more on this topic:
Java Interviews image
Java Interviews

Interview - Product Companies, eCommerce Companies, Investment Banking, Healthcare Industry, Service Companies and Startups.

Last updated 1 month ago


Recommended books for interview preparation:

This website uses cookies to ensure you get the best experience on our website. more info