REPEAT - Editorial

editorial
, ,
1

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

2

This was great problem !! :smiley:

3 Likes
3

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.

4

I am unable to understand k-1. In problem, it’s given that number is repeated k times. Then how k-1 came?

5

The sum of the sequence can be calculated when the repeated number appears only once, rather than K times, so the difference between the two sums involves K{-}1 copies of the repeated number.

7

according to editorial it is 1,3…,x,…n,x,x…
so basically 1 to n is the sum of the first odd terms of the element which is n^2 then ans should be n^2 +(k-1)*x = s =>x = (s-n^2) / k-1