10042  Smith Numbers
Moderator: Board moderators
ACC 10042 ..At last
Thanks For I/O
I Got ACC Now.I forgot To Post
Thank's
Rocky
I Got ACC Now.I forgot To Post
Thank's
Rocky

 Experienced poster
 Posts: 209
 Joined: Sun Jan 16, 2005 6:22 pm
10042
Hello can anybody plz help me to understand the problem 10042?

 Experienced poster
 Posts: 154
 Joined: Sat Apr 17, 2004 9:34 am
 Location: EEE, BUET
At first make sure what a smith number is. By definition  Smith number is such a number that the sum of its digits is equal to the sum of digits of all it's prime factors (considering frequency). Let's consider the example given in the problem.
4937775 can be written as 3 * 5 * 5 * 65837  which are it's prime factors.
Now, if you sum the digits of the original number, you get (4 + 9 + 3 + 7 + 7 + 7 + 5) = 42. Again summing the digits of the prime factors leads to > {(3) + (5) + (5) + (6 + 5 + 8 + 3 + 7)} = 42. As both the sums are equal, 4937775 is a smith number.
Now, if you check the sample input, you will find 4937774 is not a smith number. Increment the number by one until you get a smith number which is the immediate next one in this case.
Similarly, if the input is 105, it's not a smith number and 106,107,108....,120  none of these are smith #. The first smith # after 105 is 121. This will be your output. Hope it helps.
4937775 can be written as 3 * 5 * 5 * 65837  which are it's prime factors.
Now, if you sum the digits of the original number, you get (4 + 9 + 3 + 7 + 7 + 7 + 5) = 42. Again summing the digits of the prime factors leads to > {(3) + (5) + (5) + (6 + 5 + 8 + 3 + 7)} = 42. As both the sums are equal, 4937775 is a smith number.
Now, if you check the sample input, you will find 4937774 is not a smith number. Increment the number by one until you get a smith number which is the immediate next one in this case.
Similarly, if the input is 105, it's not a smith number and 106,107,108....,120  none of these are smith #. The first smith # after 105 is 121. This will be your output. Hope it helps.
You should never take more than you give in the circle of life.

 Experienced poster
 Posts: 209
 Joined: Sun Jan 16, 2005 6:22 pm
Thanks
Thanks Mahmudur Bhai for your help.I now understand the problem and get ready for code.

 New poster
 Posts: 14
 Joined: Mon Mar 07, 2005 7:10 pm
 Location: Bosnia and Herzegovina
 Contact:
10042 WA
Hello!
I have problems with my program . Can anybody tell me what's wrong in the code. I use algorithm from Programming Challenges.
I have problems with my program . Can anybody tell me what's wrong in the code. I use algorithm from Programming Challenges.
Code: Select all
// 10042: Smith numbers
#include <cmath>
#include <iostream>
using namespace std;
typedef unsigned long inte;
inte sum (inte n)
{
inte r = 0;
while (n)
{
r += n % 10;
n /= 10;
}
return 0;
}
// This algorithm is from Programming challenges,
// it works for me in other ACM problems
inte ptr (inte w)
{
inte n = w;
inte rez = 0;
while (n % 2 == 0)
{
rez += 2;
n /= 2;
}
inte i = 3;
while (i <= (sqrt(n) + 1))
{
if (n % i == 0)
{
rez += sum(i);
n /= i;
}
else i += 2;
}
if (n > 1) rez += sum(n);
// If n == w ==> n is prime
if (n == w) return false;
if (sum(w) == rez) return true;
return false;
}
int main (void)
{
inte t; cin >> t;
while (t)
{
inte n; cin >> n;
while (!ptr(++n));
cout << n << endl;
}
// system("pause");
return 0;
}
You made a very careless mistake in your code. I refer you to this part of your code:
This sum function is always returning 0. I think you meant return r.
Code: Select all
inte sum (inte n)
{
inte r = 0;
while (n)
{
r += n % 10;
n /= 10;
}
return 0;
}

 New poster
 Posts: 14
 Joined: Mon Mar 07, 2005 7:10 pm
 Location: Bosnia and Herzegovina
 Contact:
10042
I dont know why judge give me wrong answer
My code is given below...
What is the problem of it...
Code: Select all
#include<stdio.h>
#include<math.h>
long long int DigSum(long long int t)
{
long long int m=0;
while(t)
{
m+=t%10;
t/=10;
}
return m;
}
long long int PrimeFactorSum(long long int t)
{
long long int k=0,i,d;
while(t%2==0)
{
k+=2;
t/=2;
}
d=sqrt(t);
for(i=3;i<=d;i+=2)
{
if(t%i==0)
{
while(t%i==0)
{
k+=DigSum(i);
t/=i;
}
d=sqrt(t);
}
}
if(t>=i)k+=DigSum(t);
return k;
}
void main()
{
long cas;
long long int sum1,sum2,n;
scanf("%ld",&cas);
while(cas)
{
scanf("%lld",&n);
while(0==0)
{
sum1=DigSum(n);
sum2=PrimeFactorSum(n);
if(sum1==sum2)break;
else n++;
}
printf("%lld\n",n);
}
}
Hi I am Masud...
Read the question carefully
Always search the forum for existing threads about your topic and use them if necessary instead of creating a new one. I'm sure you'll find a lot more help along with some test I/O if you search.For every input value n, you are to compute the smallest Smith number which is larger than n.
...prime number is not worth being a Smith number...
about SIGSEGV
hi,
in 10042 smith numbers, i try the all input from other topic and get correct answer use gcc.
but when i submit my code, it gets signal 11 (SIGSEGV). Meaning:
Invalid memory reference
but i don't know in what condition could make this mistake
is there anyone can help me? thx.
in 10042 smith numbers, i try the all input from other topic and get correct answer use gcc.
but when i submit my code, it gets signal 11 (SIGSEGV). Meaning:
Invalid memory reference
but i don't know in what condition could make this mistake
is there anyone can help me? thx.

 Experienced poster
 Posts: 136
 Joined: Fri Apr 15, 2005 3:47 pm
 Location: Singapore
 Contact:
It is possibly because of your program tried to access the invalid memory, for example if you write the code like this :
It might be error, because you made an array with capacity only 1000 but you tried to access the 1002nd array... (0 is the 1st array).
Code: Select all
int arr[1000];
arr[1001] = 5;
printf("%d\n",arr[1001]);
if my array is : int prime[20000]; and i write a function
int digitsum(unsigned long int a)
then i write
psum+=digitsum(prime);
could make SIGSEGV ?
or unsigned long int s
but s=s%prime or s/=prime
could make SIGSEGV ?
because i test all data from 0  10^9 in gcc and all answer is fine
but when i submit... get SIGSEGV
int digitsum(unsigned long int a)
then i write
psum+=digitsum(prime);
could make SIGSEGV ?
or unsigned long int s
but s=s%prime or s/=prime
could make SIGSEGV ?
because i test all data from 0  10^9 in gcc and all answer is fine
but when i submit... get SIGSEGV
finally i get accept, i found the bug is i use store primes which are <100000
, and when i test the input s, and use s to mod by prime.. if use all the primes < 100000, s still can't be 1, i wrote if (s>prime[10000]) digitsum(s)
and get RE
when i change the code to if (s!=1) the digitsum(s) directly... it's accept
thx your reply
, and when i test the input s, and use s to mod by prime.. if use all the primes < 100000, s still can't be 1, i wrote if (s>prime[10000]) digitsum(s)
and get RE
when i change the code to if (s!=1) the digitsum(s) directly... it's accept
thx your reply