1
$\begingroup$

The beauty of a number is defined as follows :-

public int beauty(long number)
{
     int count = 0;

     while( number > 0 )
     {
         count += (number & 1);
         number = number / 2;
     }

     return count;
}

Given X, we need to find the minimum N such that the sum of beauty of all numbers from 1 to N (inclusive) is at least X. X may be as large as upto 10^18 and there are 2*(10^4) test cases.

As far as I have understood, the beauty of the number is the count of set bits in the integer. So we need to find the sum of count of set-bits from 1 to N. But numbers such as X = 10^18 give the values 10^15 for N. It is not feasible to run loop from 1 to 10^15. Is there a better algorithm ?

$\endgroup$
  • $\begingroup$ The answer to “is there a better algorithm” would appear to be “yes”. Note that nobody asks you for this property for some specific n, but for the sum. So find out how to calculate the sum of some values without calculating the values. What is the sum of all integers from 1 to 1 billion (no computer, no pen and paper for calculating)? $\endgroup$ – gnasher729 Jan 7 at 10:06
1
$\begingroup$

Notations :

  • $b(x)$ is the beauty of $x$.
  • $S_c(n) = \sum_{x = 0}^{2^n-1} (b(x)+c)$ where $c\in\mathbb N$
  • $\tilde O(\log t)$ : polylogarithmic in $t$

Argument :

Let's first show that $S_c(n)$ is easy to calculate for any $c,n\in\mathbb N$. Each number in $[\![0, 2^{n-1}]\!]$ has at most $n$ bits, and for each $i\in[\![1, n]\!]$, exactly half of the numbers below $2^n$ have the $i$-th bit set to 1. Therefore, we can rewrite $$\sum_{x =0}^{2^n-1} b(x) = \sum_{i = 1}^n 2^n/2 = n\cdot 2^{n-1}$$ (in 0, the result is 0). This leads to : $$ S_c(n) = 2^{n-1}\cdot (c+2n)$$ Since $S_c(n)$ grows exponentially and is computable in $O(n)$, it takes $\tilde O(\log X)$ time to find the (unique) $n$ such that \begin{equation}S_c(n)\le X< S_c(n+1)\end{equation}

We'll note $n_0$ this $n$ for $c = 0$. One should notice that this $n_0$ is the index of the leftmost bit set to 1 in $N$ $$\sum_{x = 0}^N b(x) = \sum_{x = 0}^{2^{n_0}-1} b(x) + \sum_{x = 2^{n_0}}^N b(x)$$ Moreover, $N<2^{n+1}$, so each $x$ in the rightmost sum has $n$ bits and the leftmost bit set to 1, i.e. : $$\sum_{x = 2^n}^N b(x) = \sum_{x = 0}^{N-2^n} b(x) + 1$$

We therefore get a recursive call : we can find the index of the leftmost bit set to 1 in $N-2^n$ by finding $n_1$ such that $S_1(n_1)\le (X- S_0(n_0)) \le S_1(n_1+1)$

This lends the following algorithm :

s(n,c) =
    if n = 0 then c
    else (2^(n-1)*(c+2*n))

smallest_n(x,c,n) = //We shall call this function with n = 0
    if s(n+1,c) > x then n
    else smallest_n(x,c,n+1)

sum_beauties_above(x,c) =
    if x = 0 then 0
    else
        let n = smallest_n(x,c,0) in
        let n' = sum_beauties_above(x - s(n,c),c+1) in
        2^n + n'
sum_beauties_above(x,0)

the first function takes $O(n)$ time, the second takes $\tilde O(\log X)$. The main function calls itself as many times as $N$ has bits set to $1$, which is bounded by $\log N\le \log X$, and each call has complexity $\tilde O(\log X)$, so we keep a polylogarithmic complexity in $X$.

However, this has been written in functionnal programming style, and is not tail-recursive, therefore, it is highly suboptimal, but this way of writing seems easier to understand, and one should take care of optimization.

$\endgroup$
0
$\begingroup$

Let us first solve the following problem:

Given $n$, count the total number of 1-bits of all integers from $0$ to $n-1$.

Suppose that $n = 2^{m_1} + 2^{m_2} + \cdots + 2^{m_k}$, where $m_1 > m_2 > \cdots > m_k$; every positive integer has such a representation. We can divide the range $[0,n) := \{0,\ldots,n-1\}$ into the following ranges: $$ [0,n) = [0,2^{m_1}) + [2^{m_1}, 2^{m_1}+2^{m_2}) + \cdots + [2^{m_1} + \cdots + 2^{m_{k-1}}, 2^{m_1} + \cdots + 2^{m_k}). $$ Let's start with the first range, $[0,2^{m_1})$. This range consists of all $m_1$-bit numbers. Each particular bit is 1 exactly half the time, and so the total number of 1-bits in $[0,2^{m_1})$ is $m_12^{m_1-1}$.

The second range consists of all numbers in $[0,2^{m_2})$ to which $2^{m_1}$ was added. The additional power contributes an extra 1-bit to each number in the range, for a total of $m_2 2^{m_2-1} + 2^{m_2}$, which can also be written as $2^{m_2} (m_2/2 + 1)$.

Continuing in this way, we see that the total number of 1-bits of all integers in $[0,n)$ is $$ 2^{m_1}(m_1/2) + 2^{m_2}(m_2/2+1) + 2^{m_3}(m_3/2+2) + \cdots + 2^{m_k}(m_k/2+k-1). $$

This suggests the following algorithm:

  1. Find the maximal $m_1$ such that $\sigma_1 := 2^{m_1}(m_1/2) \leq x$. In case of equality, return $2^{m_1}-1$.
  2. Find the maximal $m_2 < m_1$ (if any) such that $\sigma_2 := \sigma_1 + 2^{m_2}(m_2/2+1) \leq x$. In case of equality, return $2^{m_1} + 2^{m_2}-1$.
  3. Continue in this way. If you get stuck at $m_1,\ldots,m_k$, return $2^{m_1} + \cdots + 2^{m_k}$.

(Getting stuck means that there is no $m_{k+1} < m_k$ such that $\sigma_{k+1} \leq x$.)

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.