CODEWITHSUNDEEP
c++algorithmbooststl
PaolaJ.
PaolaJ.

Reputation: 11532

How to on efficient and quick way add prefix to number and remove?

How to on efficient and quick way add prefix to number and remove ? (number can have arbitrary number of digits, number doesn't have limit) I have number for example 122121 and I want to add digit 9 at the begining to be 9122121, after that I need to remove first digit in number. I have split into vector, push front digit(in this case 9) and the create number from digits ( iteration with multiplying 10). Is there more efficient way ?

Upvotes: 0

Views: 760

Answers (6)

Alexander
Alexander

Reputation: 23537

I shall provide an answer that makes use of binary search and a small benchmark of the answers provided so far.

Binary Search

The following function uses binary search to find the number of digits of the desired number and appends the desired digit in front of it.

int addPrefix(int N, int digit) {
    int multiplier = 0;
    // [1, 5]
    if(N <= 100000) {
        // [1, 3]
        if(N <= 1000) {
            //[1, 2]
            if(N <= 100) {
                //[1, 1]
                if(N <= 10) {
                    multiplier = 10;
                //[2, 2]
                } else {
                    multiplier = 100;
                }
            //[3, 3]
            } else {
                multiplier = 1000;
            }
        //[4, 4]
        } else if(N <= 10000) {
            multiplier = 10000;
        //[5, 5]
        } else {
            multiplier = 100000;
        }
    //[6, 7]
    } else if(N <= 10000000) {
        //[6, 6]
        if(N <= 1000000) {
            multiplier = 1000000;
        //[7, 7]
        } else {
            multiplier = 10000000;
        }
    //[8, 9]
    } else {
        //[8, 8]
        if(N <= 100000000) {
            multiplier = 100000000;
        //[9, 9]
        } else {
            multiplier = 1000000000;
        }
    }
    return N + digit * multiplier;
}

It is rather verbose. But, it finds the number of digits for a number in the range of int in a maximum of 4 comparisons.

Benchmark

I created a small benchmark running each provided algorithm against 450 million iterations, 50 million iterations per number of determined number of digits.

int main(void) {
    int i, j, N = 2, k;
    for(i = 1; i < 9; ++i, N *= 10) {
        for(j = 1; j < 50000000; ++j) {
            k = addPrefix(N, 9);
        }
    }
    return 0;
}

The results:

+-----+-----------+-------------+----------+---------+
| run | Alexander | Daniel Frey | kkuryllo | W.B.    |
+-----+-----------+-------------+----------+---------+
| 1st |    2.204s |      3.983s |   5.145s | 23.216s |
+-----+-----------+-------------+----------+---------+
| 2nd |    2.189s |      4.044s |   5.081s | 23.484s |
+-----+-----------+-------------+----------+---------+
| 3rd |    2.197s |      4.232s |   5.043s | 23.378s |
+-----+-----------+-------------+----------+---------+
| AVG |    2.197s |      4.086s |   5.090s | 23.359s |
+-----+-----------+-------------+----------+---------+

You can find the sources used in this Gist here.

Upvotes: 2

Daniel Frey
Daniel Frey

Reputation: 56863

If you want efficiency, don't use anything else than numbers, no vectors, strings, etc. In your case:

#include <iostream>

unsigned long long add_prefix( unsigned long long number, unsigned prefix )
{
    // if you want the example marked (X) below to print "9", add this line:
    if( number == 0 ) return prefix;

    // without the above, the result of (X) would be "90"

    unsigned long long tmp = ( number >= 100000 ) ? 1000000 : 10;
    while( number >= tmp ) tmp *= 10;
    return number + prefix * tmp;
}

int main()
{
    std::cout << add_prefix( 122121, 9 ) << std::endl; // prints 9122121
    std::cout << add_prefix( 122121, 987 ) << std::endl; // prints 987122121
    std::cout << add_prefix( 1, 9 ) << std::endl; // prints 91
    std::cout << add_prefix( 0, 9 ) << std::endl; // (X) prints 9 or 90
}

but watch out for overflows. Without overflows, the above even works for multi-digit prefixes. I hope you can figure out the reverse algorithm to remove the prefix.

Edited: As Andy Prowl pointed out, one could interpret 0 as "no digits", so the prefix should not be followed by the digit 0. But I guess it depends on the OPs use-case, so I edited the code accordingly.

Upvotes: 3

W.B.
W.B.

Reputation: 5525

You can calculate number of digits using floor(log10(number)) + 1. So the code would look like:

int number = 122121;
int noDigits = floor(log10(number)) + 1;
//Add 9 in front
number += 9*pow(10,noDigits);
//Now strip the 9
number %= pow(10,noDigits);

I hope I got everything right ;)

Upvotes: 2

kkuryllo
kkuryllo

Reputation: 340

%First find the highest power of 10 greater than your number. Then multiple the addition by that and add to your number

For example:

int x;
int addition;
int y = 1;
while (y <= x)
{
    y *= 10;
}

x += addition * y;

I didn't test this code so just take as an example... I also don't really understand your other instructions, you'll need to clarify.

edit okay I think I understand that you also want to remove the first digit sometime as well. You can use a simular approach to do this.

int x;
int y = 1;
while (y <= x*10)
{
    y *= 10;
}

x %= y;

Upvotes: 1

blue
blue

Reputation: 2793

you could put the digits in an std::string and use insert and delete but it might be an overkill

Upvotes: 1

Matthew
Matthew

Reputation: 2829

How about using lexical cast from boost? That way you're not doing the iteration and all the yourself.

http://www.boost.org/doc/libs/1_53_0/doc/html/boost_lexical_cast.html

Upvotes: 1

Related Questions