Why is this program working?

[Bank]

for this question:

someone had a plan to access another person's computer and the plan was to send a huge amount of n different natural numbers from 1 to n to obtain total control over that person's energy.

But his plan failed. The reason for this was very simple: the "someone" didn't perceive any information, apart from numbers written in binary format. This means that if a number in a decimal representation contained characters apart from 0 and 1, it was not stored in the memory. Now "someone" wants to know, how many numbers were loaded successfully.

Input
Input data contains the only number n (1 ≤ n ≤ 10^9).

Output
Output the only number — answer to the problem.

Examples
input
10
output
2
input
99
output
3
input
72
output
3
input
100
output
4
Note
For n = 10 the answer includes numbers 1 and 10.

#include <iostream>

using namespace std;

ll decimaltobinary(ll n)
{
    if(n == 0) return n;
    return n%2 + 10*decimaltobinary(n/2);
}
int binarytodecimal(int num)
{
    if (!num) return num;
    return num % 10 + 2*binarytodecimal(num / 10);
}

ll result(ll m, ll k, ll n){
if(k > n) return binarytodecimal(decimaltobinary(m-2));

return result(m+1, decimaltobinary(m), n);
}


int main()
{
    ll n;
    cin >> n;
    cout << result(1,0,n);
    return 0;
}

i dont get how this "result" function works, i understand the binary to decimal and decimal to binary ofcourse but, the result function just seems too complicated i can't understand what goes on in there and how does that guy's code output correct answers for the problem? i hope someone can explain

Also, maybe I don't understand the problem clearly..idk

[ne555]

Here's an iterative version

result(n):
   for m in range(1,n)
      if decimal_to_binary(m)>n:
         return m-1

> Also, maybe I don't understand the problem clearly..idk
without knowing what you understood, it's hard to guess.

[Bank]

@ne555 but then it'd pass the time limit of "1 second" of the question if we go with a for loop cause n can be up to 10^9 and the max per 1 second is 10^7 or 10^8 on these systems, i just don't get this part specifically:

return binarytodecimal(decimaltobinary(m-2));

why m-2?

[lastchance]

#include <iostream>
using namespace std;

int main()
{
   int n, digit, result = 0, powerof2 = 1;
   cin >> n;
   while ( n > 0 )
   {
      digit = n % 10;
      if      ( digit == 1 ) result += powerof2;
      else if ( digit >  1 ) result = 2 * powerof2 - 1;
      n /= 10;
      powerof2 *= 2;
   }
   cout << result;
}

[ne555]

@Bank: the code is equivalent.
you had return result(m+1, /**/); that's a loop.

> n can be up to 10^9
the condition to end the loop is decimal_to_binary(m)>n, with `n=1e9' m would be about 512
if you prefer

K=1
while decimal_to_binary(K)<=n:
   K += 1
return K-1

> why m-2?
because the code is obfuscated (a clue would be that's is doing b2d( d2b(x) ), operations that cancel out)
the function receives `m+1', but works on `m', so instead of returning `m-1' it has to return `m-2'