how can I get the first 3 digits of a given unsigned long long without converting it to string and there is now the constant length of the number.

without using the naive approach of dividing with / 10.

like this

int first_3_digits(unsigned long long number)
{
    unsigned long long n = number;
    while(n >= 1000){ 
        n = n/10;
    }

    return n;
}

I had an interview and they said that this solution wasn't good enough the interviewer said the solution resembles a binary search. I know how binary search work but I don't know how to connect it to this problem.

CodePudding user response：

Finding the "best" solution often depends on the criteria you define to matter. If you want smallest or simplest solution, your approach is not bad.

If you want fasted solution (and got the hint about "binary search" from the interviewer), then you might try something like this (not tested):

int first_3_digits(unsigned long long number)
{
    unsigned long long n = number;
    unsigned long long chopped;

    // n has up to 20 digits. We need to chop up to 17 digits.

    // Chop 8 digits
    chopped = n / 100000000ull;
    if (chopped >= 100)
    {
        n = chopped;
    }
    // chopped has up to 12 digits,
    // If we use old n we have up to 11 digits
    // 9 more to go...

    // Chop 4 digits
    chopped = n / 10000ull;
    if (chopped >= 100)
    {
        n = chopped;
    }
    // chopped has up to 8 digits,
    // If we use old n we have up to 7 digits
    // 5 more to go...

    // Chop 2 digits
    chopped = n / 100ull;
    if (chopped >= 100)
    {
        n = chopped;
    }
    // chopped has up to 6 digits,
    // If we use old n we have up to 5 digits
    // 3 more to go...

    // Chop 2 digits again
    chopped = n / 100ull;
    if (chopped >= 100)
    {
        n = chopped;
    }
    // chopped has up to 4 digits,
    // If we use old n we have up to 3 digits
    // 1 more to go...

    // Chop last digit if required.
    if (n >= 1000)
    {
        n /= 10;
    }

    return n;
}

For 64 bit values, maximum number is 18446744073709551615, i.e. 20 digits. We have to remove at most 17 digits. As this is not a perfect number to use powers of 2 for number of digits to chop, we repeat the step to chop 2 digits.

That solution might be a bit faster but is likely to take more code.

CodePudding user response：

here a short solution using log10 function :

int first_n_digits(unsigned long long number){
    return number < 1000 ? number =  (int)number : number = (int)(number/pow(10,(int)(log10(number) 1)-3));
}

CodePudding user response：

You can calculate the length of a number (its power) using the decimal logarithm, then use the decimal exponent to get a divisor less than three orders of magnitude and integer divide the number by it:

#include <assert.h>
#include <math.h>

int first_3_digits(unsigned long long number)
{
     if(number < 1000)
         return number;
     int number_length = int(floor(log10l(number))) 1;
     assert(number_length > 3);
     unsigned long long divider = exp10l(number_length - 3);
     return number/divider;
}

int main()
{
     assert(first_3_digits(0)==0);
     assert(first_3_digits(999)==999);
     assert(first_3_digits(1234)==123);
     assert(first_3_digits(9876543210123456789ull)==987);
     return 0;
}