find single repeating number from a big array

Carvia Tech | May 05, 2019 | 1 min read | 138 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. BlackRock Top Java Interview Questions: Investment Banking Domain
  2. Cracking core java interviews - question bank
  3. Morgan Stanley Investment Banking Java Interview Questions
  4. Goldman Sachs Java Interview Questions for Senior Developer
  5. ION Trading Java Interview Questions
  6. Citibank Java developer interview questions
  7. Top 50 Multi-threading Java Interview Questions for Investment Bank


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 week ago


Recommended books for interview preparation:

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