1

I'm trying to solve this problem:

Given an integer k, find the least integer n such that the total number of ones in the binary representations of { 1, 2, . . ., n } is at least k.

For example, given k = 4, we want n = 3, because the binary representations of 1, 2, and 3 contain 1, 1, and 2 ones (respectively), and 1 + 1 + 2 ≥ 4.

I have tried using counting the set bits from (1 to n) in Log(n),Unable to find minimum n with efficient way.

Edit :

Code : Calculating no. of set bits from 1 to n (Reference) but problem in finding minimum n.Is there any way to derive some solution around this ?

int getSetBitsFromOneToN(int N){ 
int two = 2,ans = 0; 
int n = N; 
while(n){ 
    ans += (N/two)*(two>>1); 
    if((N&(two-1)) > (two>>1)-1) ans += (N&(two-1)) - (two>>1)+1; 
    two <<= 1; 
    n >>= 1; 
} 
return ans; 
} 
Community
  • 1
  • 1
  • 3
    Please post what you tried, preferably a [mcve]. – R Sahu Jan 06 '19 at 07:34
  • I think you should split your answer. First part is getting the algorithm right, the second part is programming it. The first part is independent of the language, it shouldn't have a C++ tag. The second part should start with the result of the first and precisely describe the problem you have in translating the algorithm to C++. That said, as a new user, please take the [tour] and read [ask]! – Ulrich Eckhardt Jan 06 '19 at 12:47

1 Answers1

1

The algorithm is relatively simple. Instead of going one number at a time and accumulating the number of 1's its binary representation has, we will skip closer and closer to the target using a series of functions {a(m), b(m), c(m)...} to get closer to the target and leave at most a couple of numbers to add in manually in the end. Each function will be in the format where x is the number of the function (for a(m) x=0, for b(m) x=1...).

These functions are based on a trait of binary numbers: in all the numbers from 1 to you can know the accumulated number of 1's in its binary representations of {1,2...n}.

Let's look at the number , which is in binary 1111. You can know the count of 1's in all the numbers from 1 (0001) to 15 (1111) - it's counting how many ways you can put 1 in 4 places (4) times 1, plus how many times you can put 2 in 4 places (6) times 2, plus how many times you can put 3 in 4 places (4) times 3 plus how many ways you can put 4 in 4 places (1) times 4. So the total is 32, which is also . you will notice that for any such number n=, the accumulated number of 1's is . Let's name this function a(m) as decided above (x=0 here, so no need for the added element in this one). For example:

  • 1 = a(1) = = = = 1.
  • 3 = a(2) = = = = 4.
  • 7 = a(3) = = = = 12.
  • 15 = a(4) = = = = 32.
  • 31 = a(5) = = = = 80.

and so on. so for the number 15 which is , we calculate a(4) and get 32 accumulated 1's. We will also notice that the number has exactly m 1's in it (all digits set to 1).

Knowing that, you take your number k find the nearest a(m) that's smaller than k, while a(m+1) will be greater than k. If a(m+1) is only m+1 more than k, take a(m+1) as the answer and finish the algorithm. Since a(m+1) has at least m+2 in it, it means you cannot accumulate all the k 1's you need without it.

If k is more than m+1 larger than a(m+1) but is larger than a(m), you will need a second step approximation by defining a second function - let's call it b(m). We'll define b(m)=. This number will be equivalent to exactly (not as it was for the a function) For example:

  • 2 = b(1) = = = = 1+2 = 3.
  • 4 = b(2) = = = = 4+4 = 8.
  • 8 = b(3) = = = = 12+8 = 20.
  • 16 = b(4) = = = = 32+16 = 48.
  • 32 = b(5) = = = = 80+32 = 112.

The reason we defined b is to describe the unique difference in accumulation of 1's between the first batch of numbers and the second following batch of numbers - the addition of another most-significant 1 to them each of the numbers in the second batch. This is why we now look at and not .

By adding the two functions, we can get our number n. If we still run short of the final k after two approximations, we can accumulate one by one the numbers until we reach k.

Let's assume k=50. We know that a(4) is the closest we can get, being the largest number that is still below 50. a(5) would get us to 80, as we saw above. So a(4) is the first half of the solution, which is 15.

The remaining 1's is 50-32=18. We need to see how many numbers we need to process past 15 to accumulate at least 18 more 1's. from calculating the b function, we see that b(2) gets us closer and b(3) is 2 over. Since we know that the number represented by b(3) has at least 4 1's in it, we know it's the number we need - any number below it will only have accumulated 16 1's and we need 18. So we go with b(3), which is or 8. The result is 15+8=23, and that is the lowest number that has at least 50 accumulated 1's in all of the {1,2..23} binary representations.

If we need to go another iteration, we can define and it will get us even closer. For example, for k=120 we get a(5)+b(3)=100, and adding c(2) will add us 12 more to 112. We can add manually the missing 8 numbers or decide to add which will get us to 119 by adding a(5)+b(3)+c(2)+d(1). This means the next number must be the least n that has k or more 1's accumulated. a(5)=31, b(3)=8, c(2)=4 and d(1)=2 so n=46 - the next number up from the 119 1's collected by 45.

The complexity is O(log(k)) - we have log(k) steps to get a(m) and another at most log(k) accumulations to get the b(m) and our eventual n.

CODE

//This represents the function a(m), b(m)... etc.
public int getFuncResult(int funcNum, int arg) {
    Double result =  Math.pow(2,arg-1)*arg+funcNum*Math.pow(2,arg);
    return result.intValue();
}

//This is the iterative algorithm described: add a(m)+b(m)... until k
public int countOnesToKIter(int k) {
    int funcNum = 0;
    int counter = 0;
    int retVal = 0;
    int exponent = 0;
    while (k > 0) {
        //for the current function, find the appropriate m
        while (k > counter) {
            exponent++;
            counter = getFuncResult(funcNum, exponent);
        }

        //if the last number contains more 1's than the difference, use it.
        if (counter-k < exponent) {
            counter=getFuncResult(funcNum, exponent-2);
            retVal+=Math.pow(2,exponent-2);
        } else {
            counter = getFuncResult(funcNum, exponent-1);
            retVal+=Math.pow(2,exponent-1);
        }
        funcNum ++;
        exponent=0;
        k = k-counter;
        counter = 0;
    }

    return retVal;
}
Assafs
  • 3,257
  • 4
  • 26
  • 39
  • once i get right m how can we reach to exact n that is not clear can you please explain little bit –  Jan 06 '19 at 09:24
  • Give me a little time to edit, I'll add this step into the answer and update. – Assafs Jan 06 '19 at 09:50
  • Done, have a look. I got you two approximations, which is the best you could get. You first calculate which a(m) gets you the closest, and then if needed calculate b(m) to get you even closer still. – Assafs Jan 06 '19 at 10:45
  • That’s because you need a(3)=12, and not a(2). The a(3) has 4 1’s in it (7 is represented by 1111) so any number below it will only have at most 8 1’s which means a(3) is the least n you can find with over 11 1’s. Note my comment right after the a(m) examples. – Assafs Jan 06 '19 at 11:17
  • Can you check is this correct way of finding minimum m what i understood : https://ideone.com/oQ4f7S –  Jan 06 '19 at 11:41
  • I added more detailed comments on the algorithm. It is basically: 1) calculate the nearest a(m). If a(m+1) is just over k by m+1 at most, use a(m+1) and finish. If a(m+1) is much larger than k, use a(m) and calculate b in a similar way and add that to a(m). – Assafs Jan 06 '19 at 11:48
  • chec this https://ideone.com/UuB9YP ,I have tried on k=40 it should give 19 but giving 18 according to logic, its not always giving minimum –  Jan 06 '19 at 12:02
  • You are right! the b function related to 2^m, and not 2^m-1. I corrected it. As for your code - I only know the Java syntax so I cannot comment on it. I'm can help with the algorithm, not the specific implementation. So in your case it's 19, not 18 for k=40. Also 23 and not 22 for k=50. I appreciate your checking. – Assafs Jan 06 '19 at 12:40
  • Still it has some problem for K=1000 its giving 254 it should give 252,I think there is problem in finding minimum n –  Jan 06 '19 at 13:31
  • Hi James. My algorithm will only get you close to your result by skipping calculations. Using k=1000 working my algorithm will get a(7)+b(6) which will tell you that the number 191 has accumulated 704 1's in its path {1,2...191}. you will need to accumulate the remainder individually - go from 191 to 252 and add the 1's in each number to the total until you reach 1000. I don't know how you got to 254 exactly, but in pen and paper it seems like you can't get closer than 704. I'll see if I can extend the algorithm from 2-phase to n-phase, getting you even closer to the target. – Assafs Jan 06 '19 at 14:19
  • @james I got your algorithm extended to a complete log approximation, using log(n) iterations at most to get you your number. I will write some code to test this in Java and confirm it's easy to use. – Assafs Jan 06 '19 at 15:07
  • Can you share your code link i will go through once –  Jan 06 '19 at 16:45
  • @james added the code. It works beautifully for all the values I checked against a control test that just accumulates the 1's one at a time. – Assafs Jan 06 '19 at 18:18