# comparing large amounts of data

Hi everybody,

could anybody help me with the following task:

i have an array of data: adata[n].
now (at least) k elements of this array are equal, but i don't know which. comparing two elements is very time expensive, so i want to do this task with comparing as little elements as possible.
how could i get the indices of the equal elements?

k is greater than n/2, so that there can only be one solution.
also k elements of the elements should be equal, but this is not sure.
it should also be possible to determine fast if there are (at least) k equal elements in the array.

• You should keep the data in two hash-tables instead and go from there. This would give constant time-complexity of your operations.

: Hi everybody,
:
: could anybody help me with the following task:
:
: i have an array of data: adata[n].
: now (at least) k elements of this array are equal, but i don't know which. comparing two elements is very time expensive, so i want to do this task with comparing as little elements as possible.
: how could i get the indices of the equal elements?
:
: k is greater than n/2, so that there can only be one solution.
: also k elements of the elements should be equal, but this is not sure.
: it should also be possible to determine fast if there are (at least) k equal elements in the array.
:
:

• The actual problem: I'm reading sectors from a compact disc which is probably dirty and scratched. I read them n times, and then want to find out which one is the sector actually on the cd. now i say: at least k elements have to be equal, then this must be the sector actually found on the cd.
but i have already found a solution with the help of my math teacher.

: You should keep the data in two hash-tables instead and go from there. This would give constant time-complexity of your operations.
:
:
: : Hi everybody,
: :
: : could anybody help me with the following task:
: :
: : i have an array of data: adata[n].
: : now (at least) k elements of this array are equal, but i don't know which. comparing two elements is very time expensive, so i want to do this task with comparing as little elements as possible.
: : how could i get the indices of the equal elements?
: :
: : k is greater than n/2, so that there can only be one solution.
: : also k elements of the elements should be equal, but this is not sure.
: : it should also be possible to determine fast if there are (at least) k equal elements in the array.
: :
: : Thanks for your help.
: :
:
:

• You can use an ASM dll wich contains
repnz scasb
. Asm is Quick to run, so you can compare large amount of ram data easly.
Download nasm at cryogen.com . Take in mind that nasm do NOT compile as the other compilator.