Hints:

1. No sorting. It's useless. Quiqsort - too much memory, Bublesort - too long time.

2. We just need a number that is more than n/2. It always exists.

3. Read values step by step, remember the 'candidate' answer and counter increase or decrease it.

e.g:

3->3 cnt=0+1=1

3->3 cnt=1+1=2

2->3 cnt=2-1=1

2->3 cnt=1-1=0

3->3 cnt=0+1=1

Note 1:

e.g.

5

3

3

2

2

6

My program's answer is 6, but such a case never occurs (!).

"He knows exactly that more than half banknotes have the same value."

Note 2:

C# - "Memory limit exceeded 21"

use this:

    if (i % 1000 == 0)

       GC.Collect();

Regards

Edited by author 12.01.2022 20:54