Unexpected output of c++ program

Question

I was solving http://codeforces.com/problemset/problem/552/B.

In my first attempt I came up with something like:

#include <bits/stdc++.h>
using namespace std;
int digit(long a){
    int i=0;
    while(a){
        a/=10;
        i++;
    }
    return i;
}
int main()
{
    long n;
    long long s=0;
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n;
    int dig=digit(n),i=0;
    while(i<dig){
        s+=(n-pow(10,i)+1);
        i++;
    }
    cout<<s;
    return 0;
}

But for input

1000000

My program outputed

5888895

I was expecting

5888896

In my second try I wrote pow function for myself:

#include <bits/stdc++.h>
using namespace std;
int digit(long a){
    int i=0;
    while(a){
        a/=10;
        i++;
    }
    return i;
}
long long pow1(int a){
    long long s=1;
    while(a--){
        s*=10;
    }
    return s;
}
int main()
{
    long n;
    long long s=0;
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n;
    int dig=digit(n),i=0;
    while(i<dig){
        long long aux=pow1(i);
        s+=(n-aux+1);
        i++;
    }
    cout<<s;


    return 0;
}

And this time it was correct.How can one explain the working behind it?

Answer 1

The problem with the built-in pow function is that is does not work as accurate as your function. pow calculates x to the y as exp(y*log(x)). This generic formula works with all (even non-integral) exponents, and its performance is (mostly) independent on the arguments. The problem with that formula is, that pow(10,2) might be 99.9, which gets truncated to 99 when it is converted to an integer type. Try pow(10,i) + 0.5 to perform proper rounding.

Answer 2

You just need to multiply pow(10,i-1) with 0.1. That will do the work you needed.

#include <iostream>
#include <cmath>
using namespace std;
int digit_calc(long long num);
long long digit_counter(long long num, int digit);
int main()
{
    long long num,digit,total;
    cin>>num;
    digit=digit_calc(num);
    total=digit_counter(num, digit);
    cout<<total<<endl;
    return 0;
}
int digit_calc(long long num){
    int digit=0;
    while(num){
        digit++;
        num=num/10;
    }
    return digit;
}
long long digit_counter(long long num, int digit){
    long long sup,net,total=0;
    while(num){
        sup=0.1*(pow(10,digit)-1);
        net=num-sup;
        total=total+(net*digit);
        num=sup;
        digit--;
    }
    return total;
}

It passed all test cases on codeforce.

Answer 3

You may not need pow here. This works as expected and is faster too.

#include <iostream>
typedef unsigned long long ull;
using namespace std;

ull count(ull n) {
    ull i = 0;
    for (; n; ++i) n /= 10;
    return i;
}

int main() {
    ull n;
    cin >> n;
    ull digits = count(n);
    ull ans = digits * (n + 1);
    for (ull i = 0, j = 1; i < digits; ++i, j *= 10)
        ans -= j;
    cout << ans;
    return 0;
}

All testcases passed on codeforces.com