how can I speed this program up?

[jasmin]

hello,
this is my exam's Question and it should run in 1 min for 1000000000000000(15 zeros) but It takes a long time what should i do? (the Question is: how many numbers does (1 - N) have if we cin any N between 1 and 1o^15.for example n=11: 1234567891011 has 13 numbers this program should run in less than 1 min for 10^15! )

#include<iostream>

int numof_num (long long int);

using namespace std;
int main()
{
int i, sum=0;
long long int n;
cin>>n;
for (i=1 ; i<=n ; i++)
sum+=numof_num (i);
cout<<sum<<endl;
return 0;
}

int numof_num (long long int i)
{
int count=0;
while (i>0)
{
i/=10;
count++;
}
return count;
}

[Computergeek01]

Wow, we've gone from doing homework assignments to enitre exams now! Look at us guys! I hope you mean this is a practice exam?

EDIT: Sorry, I am working on your problem and I do intend to help btw.

REEDIT: The problem so far is that 10^15 is too large for a long integer, so even if you get it to compile somehow it won't run to completion.

Was this code given to you or is this what you came up with?

[Computergeek01]

New question: Are we allowed to cast the users input into a string so that we can parse it and handle each set of numbers as a sepereate array?

[Duthomhas]

His question is missing information, but to get the number of digits in an integer, use the logarithm function.

The number of digits in a number is:

└ log10 n ┘ + 1

That is easy enough to express in C++

#include <cmath> 

number_of_digits = (n == 0) ? 1 : (unsigned long)(log10( n ) + 1);

(Remember that the floor() function is biased, and you must use non-negative values for n.)

Hope this helps.

[Computergeek01]

Wow, it looks like I went about that one completly wrong. Thanks for bailing me out Duoas.

[Browni3141]

It looks to me like he is trying to get the sum of the digits of all numbers from 1 to N. If I am right this is impossible to do in a reasonable amount of time by testing every number. You need to think of a solution that doesn't rely on brute force.

[Computergeek01]

Nah, just parse the number into smaller pieces then brute force and multi-thread the B**** until it works!!! Viva Brute Force! Yay Rainbow Tables!

[kbw]

You can threads to improve the performance, the task is well suited to parallel computation.

[Browni3141]

You can threads to improve the performance, the task is well suited to parallel computation.

I highly doubt the OP could do that. There is probably a way to complete this in well under a minute. There is also probably a way to complete this in well under a second.
Figure it out.

[Duthomhas]

Use some basic math and you'll have it under a second.

[rocketboy9000]

Actually the problem was to count the number of digits displayed when a program counts from 1 to N.
I've solved it for O(logN), so tell me if you get it.

#include "stdio.h"
#include "stdlib.h"
long long tenchart[20]={0,1};
inline long long ten(int x){return tenchart[x+1];}
long long ndct(long long n,int x){
	if(n<10)return n*(x+1)*ten(x);//number of digits
	else return ndct(n/10,x+1)//major tens
	-(ten(x+1)-1)//the 1 to 10^X-1 have one less digit
	+n%10*(x+2)*ten(x);//remainder
}
int main(){
	char c[100];
	int i=1;
	long long n;
	while(++i < 20)tenchart[i]=tenchart[i-1]*10;
	sscanf(fgets(c,100,stdin),"%Ld",&n);
	printf("%lld\n",ndct(n,0));
}

[kbw]

I've got some homework, do you mind doing that too?

[rocketboy9000]

Only if it's good practice for my programming contest, lol.
No srsly, I think it was clear he's not coming back.

[jasmin]

thank you so much guys! I didnt have access to internet today something went wrong in university. but I am reading the answers now.and I am a she not he! I just thougth of something while I was at university what do you think about this code ?
#include <iostream>
#include <cstdlib>
using namespace std;

int main(int argc, int *argv[])
{
long long int x, y, w;
int m[40], k[40];
int a = 0;
int b = 0;
int i=0;
cout << "enter number";
cin >> y;
while ( i < 30)
{
m[i] = 0;
k[i] = 0;
i++;
}
w = y/3000;
x = 2101500* w;

for (int i = 0; i < 30; i++)
{
m[i] = x % 10;
x /= 10;
}
a = 0;
b = 0;
for (int i = 0; i < 30; i++)
{
b = (k[i] + m[i] + a) / 10;
k[i] = (k[i] + m[i] + a) % 10;
a = b;
}
for (int i = 0; i < 30; i++)
m[i] = 0;

x = ((w * (w - 1)) / 2) * 14 * 3;

for (int i = 0; i < 30; i++)
{
m[i] = x % 10;
x/= 10;
}

while (int i = 29 && i >= 5)
{
m[i] = m[i - 5];
i--;
}
for (int i = 0; i < 5; i++)
m[i] = 0;
a = 0;
b = 0;
for (int i = 0; i < 30; i++)
{
b = (k[i] + m[i] + a) / 10;
k[i] = (k[i] + m[i] + a) % 10;
a = b;
}
for (int i = 0; i < 30; i++)
m[i] = 0;

x= 0;
for (long long int i = 3000* w + 1; i <= y; i++)
{
if (i % 3 == 0 || i % 5 == 0)
x += i;
}

for (int i = 0; i < 30; i++)
{
m[i] = x % 10;
x /= 10;
}
a = 0;
b = 0;
for (int i = 0; i < 30; i++)
{
b = (k[i] + m[i] + a) / 10;
k[i] = (k[i] + m[i] + a) % 10;
a = b;
}
for (int i = 0; i < 30; i++)
m[i] = 0;

for (int i = 29; i >= 0; i--)
{
if (k[i] != 0)
{
for (int j = i; j >= 0; j--)
cout << k[j];
cout << endl;
break;
}
}


system("PAUSE");
return EXIT_SUCCESS; ;
}

[jasmin]

@kbw: sry sir he is not doing my home work its problem I couldnt solve and I asked for help !and Im working on my homework myself too. thanks for help any way