the most efficient way to calculate the number of digits from 1 to n

[PlusPower]

Hello !
I've tried to make a program that calculates the number of digits in a sequence of numbers from 1 to n.For instance if n is 18 it should output 27.I used a for and a while loop.It's not a problem for small numbers but it takes too much for my program to output the result for large numbers.It takes more than 20 sec.for numbers > 1000000000.
I want a more efficient way to do it,something < 0.1 sec.
I know that from 1 to 9 = 9 digits,10 - 99 = 18*9 = 162 digits and so on.But how can I do this in my program for the specific number n??
Any help would be appreciated. Thanks in advance !

[Ryan Moroz]

Hey, this is actually very simple using basic things we would learn in first year comp sic. I actually did a project like this. Takes very little time and you can add more "If" statements to the code for larger numbers as well. This will do any sum of digits for up to 999.

#include <cstdlib>
#include <cstdio>

using namespace std;


int main() {
	int num=0;
	int sum=0;

	printf("Enter a number: ");
	scanf("%i", &num);

	for(int i=1; i<=num; i++)
	{
		if (i<10)
		{
			sum=sum+1;
		}
		if ((i>=10) && (i<100))
		{
			sum=sum+2;
		}
		if (i>=100)
		{
			sum=sum+3;
		}
	}
	printf("%i", sum);

  return EXIT_SUCCESS;
}

Hope that helps, its written in first year, took my project code for you to see this. There are other ways but this is the simplest I can think of still to date.

You also have to remember, as learned with the memory functions, the speed of the process is determined by the speed of the CPU, to say it will take more than 20 seconds will be determined on the speed of the CPU and memory, not just the code.

If you are looking for a way to do this without looping from 1 - n and adding the sums, I am actually stumped but gives me something to do on a saturday afternoon.

[Ryan Moroz]

Using this coding, it took my computer about 10 seconds to calculate 999999999

#include <cstdlib>
#include <cstdio>

using namespace std;


int main() {
	int num=0;
	int sum=0;

	printf("Enter a number: ");
	scanf("%i", &num);

	for(int i=1; i<=num; i++)
	{
		if (i<10)
		{
			sum=sum+1;
		}
		if ((i>=10) && (i<100))
		{
			sum=sum+2;
		}
		if ((i>=100) && (i<1000))
		{
			sum=sum+3;
		}
		if ((i>=1000) && (i<10000))
		{
			sum=sum+4;
		}
		if ((i>=10000) && (i<100000))
		{
			sum=sum+5;
		}
		if ((i>=100000) && (i<1000000))
		{
			sum=sum+6;
		}
		if ((i>=1000000) && (i<10000000))
		{
			sum=sum+7;
		}
		if ((i>=10000000) && (i<100000000))
		{
			sum=sum+8;
		}
		if ((i>=100000000) && (i<1000000000))
		{
			sum=sum+9;
		}
		if (i>=1000000000)
		{
			sum=sum+10;
		}
	}
	printf("%i", sum);

  return EXIT_SUCCESS;
}

[PlusPower]

Yes,it really helps ! Thank you very much.It's actually very simple and it works very well :)

[Moschops]

This is a bit faster and more efficient. Watch out for overflows at big numbers; if you want more, you'll have to use a bigNum library.

#include <iostream>
#include <sstream>
#include <cmath>

int main()
{
  long long eger;
  std::cin >> eger;
  std::stringstream ss;
  ss << eger;
  std::string egerAsString = ss.str();

  int sizeOfString = egerAsString.size();
  long long johnSilver = 0, numberOfThisSize = 0;
  for (; sizeOfString >0; sizeOfString--)
  {
    numberOfThisSize = eger - (long long)pow(10,sizeOfString-1) + 1;
    int numDigitsInThatGroup = numberOfThisSize * (sizeOfString);
    eger -=  numberOfThisSize;
    johnSilver += numDigitsInThatGroup;
  }

 std::cout << "Num digits total = " << johnSilver << std::endl;
}

[D80DSL3A]

I think this is a bit more efficient:

#include<cstdio>
#include<cmath>// for the log10()

int main()
{
    int num = 1;
    printf("Enter a number: ");
    scanf("%i", &num);

    int Nd = 1 + (int)log10(num);// # of digits in the number num
    int sum = 0;
    int tenPow = 1;// in the loop tenPow = 1, 10, 100, ...

    for(int d=1; d<Nd; ++d)
    {
        sum += 9*tenPow*d;
        tenPow *= 10;
    }
    sum += Nd*( num + 1 - tenPow );// last term
    printf("sum = %i", sum);

    return 0;
}

EDIT: Didn't see Moschops post. His is probably about the same for efficiency. ie. 1 iteration per digit in num.
@xerzi Huh?

[o1vk4iN6]

bleh :/

[Fredllman]

A more efficient way to do this is to notice that all the numbers give a unit digit, all but the first 9 give a tens digit and so on.

#include <iostream>

// Total number of digits need to write all the numbers 1...n
int numDigits(int n) {
    int result = 0;
    
    for (int p = 1; p <= n; p *= 10) {
        result += n - p + 1;
    }
    
    return result;
}

int main(int argc, char** argv) {
    int n = 0;
    while (n <= 0) {
        std::cout << "Enter a number: ";
        std::cin >> n;
    }

    std::cout << "Total number of digits: " << numDigits(n);
    
    return 0;
}

[Vins3Xtreme]

just try this code:

unsigned int  numDigits(unsigned int n){
    if (n<=9) return n;
    unsigned int pos=9;
    unsigned int i=1;
    unsigned int m1,m2=n/10;
    unsigned int range=9;
    while((m1=m2/10)!=0){
        ++i;
        range*=10;
        pos+=(i * range);
        m2=m1;
    }
    pos += ((i+1)*(n - (10*i) + 1));
    return pos;
}

he just calculate in less then 1 sec. for the number 99999999 ;)

[Duthomhas]

You are all going about it the iterative way. Why not just calculate the digit count?
(It's fun!)

[Moschops]

As the kidz say, Code or get out :) Lets see your code to calculate it.

[Gaminic]

While I was typing my interpretation of Duoas' post, I realized I was explaining the logic behind the last two code snippets.

I don't know if there's a general formula for it, but it seems to me like one iteration per digit of the ending value 'n' is as efficient as you'd need it to be.

[Moschops]

It's here.

http://oeis.org/A058183

[Gaminic]

Considering the logs and powers involved, would that even be faster than the few iterations involved in the "iterated" method?

[Moschops]

Don't know. Looks elegant, though :)

[Duthomhas]

Hmm... I was actually thinking of playing with nines.

[Duthomhas]

Sorry I don't have much time to mess around right now, but here's something I hacked together to demonstrate what I was thinking.

Notice: NO LOOPS!

// nines.cpp
//----------------------------------------------------------------------------
// Calculate the number of digits produced when writing 1 to N
//----------------------------------------------------------------------------
// See http://www.cplusplus.com/forum/general/59883

//         Copyright (c) 2012 Michael Thomas Greer
// Distributed under the Boost Software License, Version 1.0.
//    ( See accompanying file LICENSE_1_0.txt or copy at
//          http://www.boost.org/LICENSE_1_0.txt )
//

#include <algorithm>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <sstream>
#include <string>
using namespace std;


//----------------------------------------------------------------------------
// number
//----------------------------------------------------------------------------
// description
//   A VERY SIMPLE bignum class.
//   Please don't base your bignums on this!
//   It does things wonkily, and only does enough to make += -= and * work.
//   Some crunching used to discourage use and to preserve space.
//
//   Numbers are unsigned, and represented as their textual equivalent.
//
#define bm bind2nd( minus <char> (), '0' )
#define bp( x ) bind2nd( plus <char> (), x )
#define c  const
#define e  erase
#define f  for_each
#define h  *this
#define i  insert
#define l  length()
#define N  number
#define o  operator
#define p  public
#define r  return
#define rb rbegin()
#define re rend()
#define ri reverse_iterator x =
#define S  string
#define t  transform
#define ul unsigned long
#define T  10
#define Z  '0'

struct number: string
  { p: N(ul _=0){o=(_);}
  N& o=(ul _){clear();do i(0,1,(_%T)+Z);while(_/=T);r h;}
  N(c S&_):S(_){}
  struct y{int k; y(int k):k(k){}void o()(char&_){k+=_-Z-Z;_=(k%T)+Z;k/=T;}};
  N& o+=(c N&_){i(0,((l<_.l)?(_.l-l):0)+1,Z);
  ri t(_.rb,_.re,rb,rb,plus<char>());
  t(x,re,x,bp(Z));f(rb,re,bp(9));f(rb,re,y(0));if(o[](0)==Z) e(0,1);r h;}
  N& o-=(c N&_){t(rb,re,rb,bp(9));ri t(rb,rb+_.l,_.rb,rb,minus<char>());
  t(x,re,x,bm);t(rb,re,rb,bp(Z+Z));f(rb,re,y(1));e(0,find_first_not_of(Z));
  r h;}
  N o*(c N&_)c{if(l<_.l)r _.o*(h);N R;R.resize(l+_.l,0);int y=0;
  for(size_t ni=0;ni<_.l;ni++){int rx=ni;for(size_t x=0;x<l;x++){
  y+=R[R.l-1-rx]+((o[](l-1-x)-Z)*(_[_.l-1-ni]-Z));R[R.l-1-rx++]=y%T;y/=T;}
  R[R.l-1-rx]=y;y=0;}t(R.rb,R.re,R.rb,bp(Z));R.e(0,R.find_first_not_of(Z));
  if(R.empty())R=S("0");r R;}
  };


//----------------------------------------------------------------------------
// Main Program
//----------------------------------------------------------------------------

//----------------------------------------------------------------------------
// Method 1: Cheat by printing all the numbers and counting how many
//           characters were printed.
//
unsigned long cheat( unsigned long n )
  {
  ostringstream ss;
  for (unsigned long x = 1; x <= n; x++)
    ss << x;
  return ss.str().length();
  }

//----------------------------------------------------------------------------
// Method 2: Using machine integers
//
// This method requires a little geometric thinking. If you want to count
// how many desks there are in a room, you multiply the number of desks
// across the front and the number of desks deep.
//
//    D   D   D   D                    
//    D   D   D   D  3 desks deep      4 x 3 desks is 12 desks total
//    D   D   D   D
//      4 desks across the front
//
// This algorithm works on the same principle. Take the argument number (n)
// and determine the number of digits wide it is (w).
//
// Multiply n and w together.
//
// Of course, smaller numbers may not be as wide as larger numbers. We can
// think of this as missing desks. (Where desks == digits.) Fortunately, the
// counting numbers have missing desk-digits which follow a friendly pattern
// involving NINES.
//
// If w is 1, then we don't need to subtract anything, since there aren't any
// missing desk-digits.
//
// If w is 2, then we need to subtract 9 for the desks in rows 1 through 9.
//
// If w is 3, then we ALSO need to subtract 99 for the desks in rows 1 through
// 99.
//
// And so on. The fun trick is that you can easily write the sum of the
// sequence 9 + 99 + 999 + 9999 + ... for any term by a simple trick and a
// single subtraction:
//
//   If we wish to know the sum of terms 1 through m, write m ones followed by
//   a single zero, and subtract m from that number.
//
// For example, if m is 3, then write "1110 - 3"; the answer is 1107. The sum
// 9 + 99 + 999 is exactly 1107. Neat, no?
//
// Using mathematics, the way to get all those ones is a simple trick with
// exponents. To get 'm' ones:
//
//    ((10**m) - 1) / 9                   (where ** represents exponentiation)
//
// We will also use w-1 for m. Take a second to think about why.
// So the equation boils down to:
//
//   (n * w) - (  (((10**(w-1)) - 1) / 9 * 10)  -  (w-1)  )
//
// :O)
//
unsigned long digits_in_1_to_N( unsigned long n )
  {
  if (n == 0) return 0;

  unsigned long w = floor( log10( n ) ) + 1;
  n *= w;
  w -= 1;
  n -= ((unsigned long)((pow( 10, w ) - 1) / 9) * 10) - w;

  return n;
  }

//----------------------------------------------------------------------------
// Method 3: Using bignums
//           This method is otherwise exactly the same as Method 3 above.
//
number& big_digits_in_1_to_N( number& n )
  {
  if (n == "0") return n;

  unsigned long w = n.length();
  n = n * number( w );
  w -= 1;
  n += number( w );
  n -= number( string( w, '1' ) + "0" );  // Forget math, we're using strings. ;O)

  return n;
  }

//----------------------------------------------------------------------------
int main()
  {
  string        s;
  unsigned long n;

  cout << "Calculate the number of digits needed to count from 1 to n.\n";

  cout << "n? ";
  getline( cin, s );

  if (s.find_first_not_of( "0123456789" ) != string::npos)
    {
    cout << "n must be a whole number, foo.\n";
    return 1;
    }

  istringstream ss( s );
  ss >> n;

  if (ss)
    {
    if (n < 10000000) // cheat method is SLOW, so we'll apply an arbitrary cut-off
      {
      cout << "ostream.str().length()  --> " << cheat( n )                 << endl;
      }

    if (n > 489564266)
      cout << "(notice how n is now too big for the machine method to work properly?)\n";
    cout <<   "unsigned int calculated --> " << digits_in_1_to_N( n )      << endl;
    }

  number nn( s );
  cout <<     "bignum calculated       --> " << big_digits_in_1_to_N( nn ) << endl;

  return 0;
  }

Enjoy!

[JLBorges]

int ndigits( int number ) // helpful comments have been deliberately omitted
{
    int digits = 0 ;
    int nd = 1 ;

    for( int i = 9 ; number > i ; i *= 10 ) { digits += i*nd ; ++nd ; number -= i ; }

    return digits + number*nd ;
}

[Duthomhas]

but... you're still playing with loops.

[JLBorges]

Yes, the answer requires summing up the terms of a series.

One loop, not two. Both log10() and pow() require loops; and the log10() loop is an expensive one involving floating point computations. Would normally be available in hardware (microcode) though.