640 - Self Numbers

[Ryan Pai]

Close.

All of those numbers are self-numbers, but you're missing one.

[Arm.Turbo]

Thx Ryan Pai
I AC now.

[wolf]

Hi all !
I wrote a program, which solvs the problem, but runing sth about 50 sec on my computer !!! How to make it faster ?

[cpp]
#include <iostream>
#include <conio.h>

using namespace std;

int sum_of_digits(long n)
{
long k,power;
int sum;
for (power=1;;power*=10)
{
if (n/power==0) break;
}
power/=10;
for (k=power;k>1;k/=10)
{
sum+=n/k;
n%=k;
}
sum+=n;
return sum;
}

int isself(long l)
{
long j,temp;
for (j=l-1;;j--)
{
temp=sum_of_digits(j);
if (temp+j==l) return 0;
if (temp+j<l) return 1;
}
}

int main()
{
for (long i=1;i<=1000000;)
{
if (isself(i)==1)
{
cout << i << endl;
}
if (i+2%2!=0)
{
if (isself(i+2)==1) i+=2; else i+=11;
}
else i+=11;
}
return 0;
}
[/cpp]

[oldbam]

Hi! I saw that some guys solved 640 in 0.00 or something like that. Is it possible to find such a quick algorithm or they just did precalculation?

[Ivor]

It isn't possible to solve this in 0.000 at all. The time I have is the result of the glitch in the system some two years ago. Else I would have time around 0.010-0.020. That is a possible time. With good IO and a trick to generation of the numbers.

Cheers,
Ivor

[akhter900]

++++++++++++++++++++++++++++++++++++

O YES,

THANKS A LOT.
&
SORRY FOR LATE THANKS.

++++++++++++++++++++++++++++++++++++

[I LIKE GN]

How can I generate FASTER I/O
Mine is 0:00.391

[Lord Nemrod]

Dear Cyfra.
I have actually solved the problem the way you are advising to do, and it does generate all self numbers, but it takes around 5 minutes to do it? Any better suggesstions?

[Sedefcho]

A better approach could be to first pre-calculate all self-numbers
from 1 to 1000000 using a technique similar to the
Eratosthenes Sieve ( although the logical checks in the algorithm
and actually the whole logic are quite different ).

Then, as a second step, you just loop and print the self-numbers.

Please let me know if you need more details.

P.A.Petrov ( Sedefcho )

[Lord Nemrod]

Well, in fact I DO need details:) if you would be so kind to provide any...
Thx

[mohsincsedu]

Hi All.............................

Plz tell me efficient Algorithm.

I got TLE.

Here is my code:

Code: Select all

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define MAX 1000000

char table[MAX+2];

long long sumdigit(long long n)
{
	long long sum = 0;
	while(n>0)
	{
		sum+=(n%10);
		n/=10;
	}
	return sum;
}


void unself(long long n)
{
	long long i, sum;
	i = n;
	while(i<=MAX)
	{
		sum = sumdigit(i);
		i+=sum;
		//if(i<=MAX)
		table[i] = '1';

	}
}



void main()
{
	long long i;
	memset(table,'0',MAX);

	for(i = 1;i<=MAX;i++)
	{
		if(table[i]=='0')
		{
			printf("%lld\n",i);
			unself(i);
		}
	}

}

Pls help me!!!!!!!



Thanks in advence!!!

[Solaris]

hmm...

Well there is no reason why ur code should NOT get TLE. you are running a code with a complexity of O(1000000*1000000).

Your problem is in the unself part. You dont have to generate the whole sequence ... just cut off the number that can be generated by the current number i.e. 'n'.

[jagadeesh]

dear
i am new to this group
one of my student has derived a formulae to generate self numbers
that tooat the age of 16
it was approved by the cochin university
and he was congratulated by his highness the president of india
i am a mathematics teacher
i want to discuss this
and to introduce the boy to this group
kindly inform what to do

[jagadeesh]

dears
i am new to this group
one of my student has derived a formulae for this
and that too at the age of 16
it was approved by the cochin university of acience and technology
and he was congratulated by his highness the president of india
he has proved googol is not a self number
and generated a formulae for this
he named the largest he found on his name
and that is 10*10^1000000
he had such immense intuition that he will deliver in seconds whether a number is a self number or not
i like to discuss this matter and like to introduce the boy to the group
i am a mathematics teacher who was working in trk higher secondary school in india
and now in mes indian school qatar
hope u all will reply
and being new i need to know how to discuss these in this group
thanking u
jagadeesh

[hamedv]

could any one say his algorithm to generate fast
sorry for my bad english!!

my time is 0.389