Founding Batch Offer ยท HLD ยท LLD ยท System Design at โ‚น799 until 30 Nov

Find Duplicate Element

Find a duplicate by subtracting expected and actual sequence sums. Students examine a shortcut that depends on every value from one through n being present.

AdvancedPhase 4 - Level 5: Logical & AppliedExample 14 of 14
find-duplicate-element.py
1# Take array
2n = int(input("Enter n: "))
3arr = []
4for i in range(n + 1):
5 arr.append(int(input(f"Element {i+1}: ")))
6
7# Find duplicate using sum
8expected_sum = n * (n + 1) // 2
9actual_sum = sum(arr)
10duplicate = actual_sum - expected_sum
11
12print(f"Duplicate: {duplicate}")

Output

Enter n: 4
Element 1: 1
Element 2: 2
Element 3: 3
Element 4: 4
Element 5: 3
Duplicate: 3

In this one

  • Infer a single extra occurrence
  • State the exact input pattern
  • Subtract expected from actual

How it works

  1. 1

    Read n + 1 values from the intended range.

  2. 2

    Compute the expected total for one through n.

  3. 3

    Subtract it from actual_sum to identify the extra value.

Edge cases

Can this handle arbitrary duplicate patterns?

Can this handle arbitrary duplicate patterns?

No. It relies on one extra occurrence and no missing range values.

What if an out-of-range value appears?

What if an out-of-range value appears?

The reported excess can be misleading.

What's going on

The input has n + 1 entries. It should contain each value one through n once, with exactly one extra occurrence of one value.

The excess actual_sum - expected_sum is then that duplicated value. This does not generally detect arbitrary duplicates: multiple extra repeats, missing values, or out-of-range values can spoil the deduction even when the arithmetic still returns a number.

Can this handle arbitrary duplicate patterns? No. It relies on one extra occurrence and no missing range values.

What if an out-of-range value appears? The reported excess can be misleading.

Quiz

Tap an option. The answer stays hidden until you pick.

Question 1

Why read n + 1 entries?

Pick an answer to check it.

Question 2

Can this handle arbitrary duplicate patterns?

Pick an answer to check it.

Questions people ask

Can this handle arbitrary duplicate patterns?

No. It relies on one extra occurrence and no missing range values.

What if an out-of-range value appears?

The reported excess can be misleading.

Why read n + 1 entries?

There is one extra occurrence beyond the n-value sequence.