REPEAT - Editorial

PROBLEM LINK:

Contest - Division 3

Contest - Division 2

Contest - Division 1

DIFFICULTY:

SIMPLE

PROBLEM:

Given an array of length N+K-1 consisting of only the first N odd numbers. Each number occurs exactly once, except for one number, which occurs K times in the array. Given S - the sum of the numbers in the array, determine the repeated element.

EXPLANATION:

Let the repeated number be X.
Reorder the elements of the array to

[1,3,\dots,X,\dots,N,X,X,\dots]

where the K-1 repeated X are placed at the end.

The sum of the first N terms is N^2 (see this for proof) and the remaining K-1 terms is (K-1)*X. The total sum is therefore:

N^2+(K-1)*X = S\\ X = \frac{S-N^2}{K-1}

which is the answer we seek!

TIME COMPLEXITY:

O(1) per test case.

SOLUTIONS:

Editorialist’s solution can be found here


Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)

  • 1
  • 2
  • 3
  • 4
  • 5

0 voters

This was great problem !! :smiley:

2 Likes

If you don’t happen upon the formula for squares, the problem is still relatively straightforward using the sum of an arithmetic progression a_1,a_2...a_n:

S_a = n(a_1 + a_n)/2

and you can easily calculate a_n since a_2 = a_1+d, a_3 = a_2+d etc. you have a_n = a_1 + d(n-1) (and in this case d=2).

So even if the base sequence were (say) 2,7,12,17,22,27,... the same process would apply - calculate the sequence sum S_a without repeats and divide the excess (S{-}S_a) by K{-}1.