I have to write an algorithm for a following problem. I have a function that has 2 parameters: an array of 32 bit unsigned whole numbers - bit vectors [ARR] and distance[dist]. We need to find how many 32 bit numbers x there are such that they are differing from each of the bit vector for the most dist bits.

Example: We have vectors: 0011, 0101 and 0101. When dist=3 then for 0000..1111 there are 13 such numbers. If dist=4 then the result is 16.

My idea is to do it with Levenshtein algorithm ( example on this website), so that I would convert the array into string.

But it would be too slow. I have a hint that we should look at the ARR and find those bits that are same in every number and therefore we need not compare them.

"For example, we have specified bit vectors with 18 fixed bits (ie we will test a total of 2 on (32-18) values) and we have given dist = 6. If you calculate for a value of x, which varies from the modified bit vectors in 6 bits, you will count just one. If it differs in less bits, for example in 5 bits, then you count 19 times (4 differences - 172x, 3 differences - 988x, ...). Think about the combinatorial problem here."

I have trouble understanding that part. Can someone please explain this to me and give me a suggestion in which direction to go?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.