0
\$\begingroup\$

Every integer can be expressed in powers of 2. You know this as the binary system

Assume you are given a set of k numbers >0 <2^n. You want to decide for this set whether every integer power of 2 up to 2^(n-1) occurs at least m times

One example:

n = 7 (2^n = 128, )
k = 5
set = 
{100,
91,
88,
63,
44}
m = 3

Solution:
Consider the binary representation of the set for up to n(=7) digits:
set = {
1100100
1011011
1011000
0111111
0101100
}
sum up the columns
{3,3,3,4,3,2,2} -> result the set failed, because 2 < m

This is so far my best(fastest) algorithm(, written for vb.net):

Private Function Check(arr As Integer(), n As Integer, m as Integer) As Boolean
    For i = n - 1 To 0 Step -1
        Dim columnCheck = 0
        For j = 0 To arr.Length - 1
            If (arr(j) And (1 << i)) <> 0 Then columnCheck += 1
        Next
        If columnCheck < m Then Return False
    Next
    Return True
End Function

maximum size of the elements of arr need to checked before entering.

Do you have better ideas?

Improve this question
\$\endgroup\$
10
  • \$\begingroup\$ It seems that we don't need n and k as input because we already have a correct set of numbers \$\endgroup\$
    – EzioMercer
    Mar 14 at 15:21
  • \$\begingroup\$ I dont have k as input. n is needed for the loop, however you can calculate this from the array. Although I dont want to do that, because im checking the different inputs not randomly, but I assume a constant n over multiple iterations. So I dont want to calculate it everytime. Assume set is generated from n not the other way around, so you know n always before u know the set. \$\endgroup\$
    – aludebe
    Mar 14 at 15:41
  • 1
    \$\begingroup\$ You probably should add the tips tag. \$\endgroup\$
    – Arnauld
    Mar 14 at 15:43
  • \$\begingroup\$ Either I should or I shouldnt, I dont see probability associated with this^^ \$\endgroup\$
    – aludebe
    Mar 14 at 15:48
  • \$\begingroup\$ I think the relative sizes of m, n, and k matter a lot for performance. For instance, is m roughly on the scale of k, or is it small? Do you know in what regime you're working in? \$\endgroup\$
    – xnor
    Mar 14 at 21:49

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.