We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Here is some G(i) values.
None of them contain a digit 0, a pair of 11 nor tripple of 222.
The digits of all G(i) values are always in increasing(or equal) order.
Since all digits of n are evaluated independently, n is not a regular integer. You can see n as a combination with repetition of digits 0-9 where the order does not matter.
Also the goal is to have the smallest value. #0 > 1# & #! + 0! == 1! + #!, therefore always use 1 instead of 0. 11 > 2 & 1! + !1 == 2!, therefore always use 2 instead of 1 & 1. 222 > 3 & 2! + 2! + 2! == 3!...
Actually, g(1) should be 0, since 0!=1, and 0 is an integer.....
However this problem considers g(1) as 1.... which is indeed, not the smallest integer which you can sum it's factorials to get 1.... 0 is.
I have implemented two different algorithms (Java/Python) and I am implementing Dynamic Programming for optimization in both of them, but it seems that's not enough for this type of problem. Any one who has implemented other method with good results?
Baby steps :)
This one is really tough. I have been dealing with this problem for almost a week and still I have not figured it out. After doing some research on DP, math induction, I was able to pass test #1 (brute force only allows you to pass test #0). Now my algorithm can calculate in fractions of secs up to g(74). I am suspecting that test #2+ are numbers where g(100)+. Any idea on how to predict?
check this one out
def fact(a):
if a==0:
return 1
else:
return a*fact(a-1)
def g(i):
n=1
h=0
while(i!=h):
sum1=0
sum2=0
k=str(n)
for u in k:
sum1=sum1+fact(int(u))
e=str(sum1)
for j in e:
sum2=sum2+int(j)
h=sum2
n=n+1
else:
return (n-1)
def res(h,m):
q=[]
d=[]
for i in range(1,h+1):
sum11=0
t=str(g(i))
if(len(t)==1):
d.append(int(t))
else:
for i in t:
sum11=sum11+int(i)
d.append(sum11)
print(sum(d)%m)
x1=int(input())
l=[]
for i in range(x1):
l.append([int(x) for x in input().split()])
for i in range(len(l)):
res(l[i][0],l[i][1])
I have a method that seems to correctly calculate g(n) for n > 63 very quickly (g(64) -> g(1000) in 0.005 sec) but for some reason from g(1) to g(63) its mostly incorrect.
However, it seems like not even this method can work within the required time constraint for tests other than #0 and #1. I believe the numbers are not much bigger than g(150), but you must calculate lots of them, since q can get up to 10^5.
I also implemented a semi-brute force method with DP, but I can only get through test #0.
why g[12] cannot be (33 or 34)and g[18] cannot be 66 and g[14] cannot be (233or 234) and g[13] cannot be (133 or 134)and g[19] cannot be 166 and g[20] cannot be 266, while g[12] can be 44 and g[13] can be 144.
Many indeed make a mistake here. A non decreasing series is the one where any a(i)>=a(j), for all i>j.
While on the other hand, if the series is said to be increasing then, it should strictly increase, which means a(i)>a(j), for all i>j.
(Here a(m) denotes the mth term of the series, and i,j,m belong to positive integers).
Thus, a series like 1,2,2,3,4,5,5,5,6,7,... must not be accounted as increasing but rather, non decreasing, as the terms never decrease but may remain the same.
I do not know how include LaTeX here in HackerRank, but I think you will get that at least.. Hope this helps!
Project Euler #254: Sums of Digit Factorials
You are viewing a single comment's thread. Return to all comments →
Here is some
G(i)values.None of them contain a digit
0, a pair of11nor tripple of222.The digits of all
G(i)values are always in increasing(or equal) order.how you find G[ greater than 45]? i got G[1-45] and at G[46] got runtime error ....
but we need value of g(i) where i can be 100 also
Agree, this problem requires a lot more thinking then being able to compute the firsts few G(i) values.
Answering 100000 queries which ask the sum all digits of G(i) values between 1 and 10^18
modm does indeed involve dicovering related concepts.I'm having the same problem! I am using int64 for storing the values. g1-45 are fast. After that it's very slow.
it is: include iostream
use BigInteger , it might help
try coding in python....you might not get any overflow errors
the issue is time......if better optimization could be done then the code would run.....python is itself slow its not the answer
Yesss same with me after 47 the processing time becomes hugee
same here after I give input greater than 45 it shows timeout error
Hey !!
Can you please tell me something briefly about : 1) Input Values 2) Output Values
I am not able get it in problem statement .
Let's take 1 query at a time and ignore the modulo.
n=4would mean :Okay got it !!!!! Just please tell me more about input values
how to find g(4)=15
What if the value exceeds more than 4 then should i have to find the g(7) and then put it to add the no.
g(3)= 5, sf( 5) = s( 5!) = s(120) = 1+2+0 = 3 how 121 will come? someone please elaborate this.
Are these actual constraints in the problem? Just curious, how did you figure this out?
These are really big hints.
Since all digits of
nare evaluated independently,nis not a regular integer. You can seenas a combination with repetition of digits0-9where the order does not matter.Also the goal is to have the smallest value.
#0 > 1# & #! + 0! == 1! + #!, therefore always use 1 instead of 0.11 > 2 & 1! + !1 == 2!, therefore always use 2 instead of 1 & 1.222 > 3 & 2! + 2! + 2! == 3!...Ahh I see! Thanks! That make sense :) So you can extend this even further to N amount of digits. 3333 is the same as 4, so on and so forth.
Ahh I see! Thanks! That make sense :) So you can extend this even further to N amount of digits. 3333 is the same as 4, so on and so forth.
Actually, g(1) should be 0, since 0!=1, and 0 is an integer..... However this problem considers g(1) as 1.... which is indeed, not the smallest integer which you can sum it's factorials to get 1.... 0 is.
g[20] is 267 or 266 ?
Since
267is the lowest possibleninsf(n)to obtain20,g(20)is267.why we need to take 20?
what is the logic to find g(i)
test values in sf() from 1 until you get it !
you are talking about getsum()?
im talking about his question how to find g(i),
bro how to get these values can you help me out
Some G(i) values are Here :-) G[49] = 133356888899 G[50] = 12245677888899 G[51] = 34446666888899 G[52] = 134446666888899 G[53] = 12245578899999999 G[54] = 123345578899999999 G[55] = 1333666799999999999 G[56] = 12245556666799999999999 G[57] = 123345556666799999999999 G[58] = 1333579999999999999999999 G[59] = 122456679999999999999999999999 G[60] = 1233456679999999999999999999999 G[61] = 13444667779999999999999999999999
how we are getting these g values ? PLz explain
I have implemented two different algorithms (Java/Python) and I am implementing Dynamic Programming for optimization in both of them, but it seems that's not enough for this type of problem. Any one who has implemented other method with good results?
Baby steps :) This one is really tough. I have been dealing with this problem for almost a week and still I have not figured it out. After doing some research on DP, math induction, I was able to pass test #1 (brute force only allows you to pass test #0). Now my algorithm can calculate in fractions of secs up to g(74). I am suspecting that test #2+ are numbers where g(100)+. Any idea on how to predict?
check this one out def fact(a): if a==0: return 1 else: return a*fact(a-1) def g(i):
n=1 h=0 while(i!=h): sum1=0 sum2=0 k=str(n) for u in k: sum1=sum1+fact(int(u))
e=str(sum1) for j in e: sum2=sum2+int(j)
h=sum2 n=n+1 else: return (n-1) def res(h,m):
q=[] d=[] for i in range(1,h+1): sum11=0 t=str(g(i)) if(len(t)==1): d.append(int(t)) else: for i in t: sum11=sum11+int(i) d.append(sum11)
print(sum(d)%m) x1=int(input()) l=[] for i in range(x1): l.append([int(x) for x in input().split()]) for i in range(len(l)): res(l[i][0],l[i][1])
I have a method that seems to correctly calculate g(n) for n > 63 very quickly (g(64) -> g(1000) in 0.005 sec) but for some reason from g(1) to g(63) its mostly incorrect.
However, it seems like not even this method can work within the required time constraint for tests other than #0 and #1. I believe the numbers are not much bigger than g(150), but you must calculate lots of them, since q can get up to 10^5.
I also implemented a semi-brute force method with DP, but I can only get through test #0.
g[12] =33 3! + 3! => 6+6 = 12 cant this be true
Your values from 41 are wrong!
There are no number
nsmaller than344479which givessf(n)=42.try g(0) its gives you value 0.
value should be minimal right so for g[12]=33 3!=6 => 6+6=12
sf(44) = s(4!+4!) = s(24+24) = s(48) = 4 + 8 = 12sf(33) = s(3!+3!) = s( 6+ 6) = s(12) = 1 + 2 = 3This is not 12.why g[12] cannot be (33 or 34)and g[18] cannot be 66 and g[14] cannot be (233or 234) and g[13] cannot be (133 or 134)and g[19] cannot be 166 and g[20] cannot be 266, while g[12] can be 44 and g[13] can be 144.
g[20] can be 266 also and which is smaller than 267
for G[12] why cant we use 33 as 3!+3!=12
g[3] already has
5as a lower value than33.like g(41) is 2355679, my code has to run 2355679 loops to find g41, it will eventually find it, but code runs out of time, how to deal with it.
what is the cindition of g[i]?? how are we calculating it?
Note that, the values of G(i) are not in "increasing" order but in "non decreasing" order.
please enlighten me with the difference
Many indeed make a mistake here. A non decreasing series is the one where any a(i)>=a(j), for all i>j. While on the other hand, if the series is said to be increasing then, it should strictly increase, which means a(i)>a(j), for all i>j. (Here a(m) denotes the mth term of the series, and i,j,m belong to positive integers). Thus, a series like 1,2,2,3,4,5,5,5,6,7,... must not be accounted as increasing but rather, non decreasing, as the terms never decrease but may remain the same. I do not know how include LaTeX here in HackerRank, but I think you will get that at least.. Hope this helps!
I wish there was a solution posted somewhere.
ill try it tomorrow
Why G(18) = 67? Shouldnt it be 66?