yavuzselim Ppl posting java/python solutions as if they coded something challenging
aniketnath283 https://www.hackerrank.com/challenges/extra-long-factorials/forum/comments/454426 Here is the java solution
nkumar7723 bhai dimag thik hai ya meme bana raha hai
A_Band Translation in english -> (Bro are you stupid or making a meme!)
munsaleem4u [deleted]saksham_g_au7 rehne de bhai isko ..kaun samjhaye issey ki yahan pe post karke sabke different solution dekh ke kuch sikthe hai
nishu_iitadv meme banara h bhai
phychessics I admit this was a little funny :D.
ipg_2016069 use bignum; $n = ;
fact=1;
for(`$i=1;$`i<=`$n;$`i++) { `$fact=$`fact*$i; } print ("$fact\n");chow_mein128 It was challenging! I had to look up JavaDocs and like, check spellings! XD
nawnaw011222 I also had to look up GeeksForGeeks LOL
stabgan Good luck on doing data science with that attitude .
nkumar7723 what kind of attitude is needed for doing sata science?
stabgan Loving python for rapid development
nishu_iitadv bhai har taraf hi muh maar rhe ho aap
janakvanani19 f=1 for i in range(n): f *= (i+1)
print(f)ganzaki Exactly hahaha
elijahtai1 My code for python3 was literally just:
print (math.factorial(n))But it was fun nonetheless.
creamyCockroach O so there is even a factorial function in python...haha I didn't now. I coded a function separately for that...thanks for the info.
PrajwalSonwaneIT i was doing the same...then i recalled
aniketruby ha ha i used recursion.
aniketruby i also didnt knew that there is a factorial function in python
kevin_debruyne ye dekh bhai python solution
n=int(input())
if n==1: print("1") else: k=n g=[] i=1
while i<n+1: g.append(k*(n-i)) k=k*(n-i) i+=1 print(max(g))
gopalgupta7799 Why are u using extra space that is list and then calculating maximum of that. You can simply calculate the factorial by directly multiplying factorial variable with decreasing n Here it is:
fact=1 while n>1: fact=fact*n n=n-1 print(fact)
Dino_7007 I'm pretty sure he was being sarcastic XD
steven_gerazdnn1 That's so true. I can understand the reason why basketball legends
mrudul_bhatt hhahahahahhahhhahahhaha
seansio1995 是啊哈哈哈哈哈哈
tsuda_kageyu It's beyond my capacity to implement a complete BigInteger like class in C++, but I did this:
#include <vector> #include <iostream> using namespace std; int main() { int n; cin >> n; vector<int> d; d.push_back(1); for (int i = 2; i <= n; ++i) { for (auto it = d.begin(); it != d.end(); ++it) *it *= i; for (size_t j = 0; j < d.size(); ++j) { if (d[j] < 10) continue; if (j == d.size() - 1) d.push_back(0); d[j + 1] += d[j] / 10; d[j] %= 10; } } for (auto it = d.rbegin(); it != d.rend(); ++it) cout << *it; return 0; }
VictoriaB Wow. This is nice!
aaron_coltrane Almost same as me
ashekhar Could you please explain the approach and why we are doing: d[j + 1] += d[j] / 10; d[j] %= 10;
squirrelwhisky He used the math multiplication method we used everyday when it's come to multiply two more-than-one-digit number: abc * ef = abc * e * 10 + abc * f . His approach is based on that but he's done it reversely. The way he did it is really clever!
clivic This solution is like mimicking the multiplication process in math, in other words, how you multiply 12 by 5:
first, 2 (in 12) by 5 is 10. Because 10/10 == 1, we got a 1 here. second, 1 (in 12) by 5. Because we got a 1 before, we get 5+1 == 6 here.
If you write it down on a paper following this code, you will get it.
squirrelwhisky Thank for you explaination. Appreciate that!
nishu_iitadv u should upvote to show ur appreciation atleast
clivic A commented C++ version using the idea of "arithmatic carry" (the same idea this example used) is as following:
void extraLongFactorials(int n) { if (n == 1) { cout << 1 << endl; return; } vector<int> digits(1, 1); for (int curr(2); curr <= n; ++curr) { auto digit_count = digits.size(); // Every digit times the number. for (int i(0); i < digit_count; ++i) { digits[i] *= curr; } // From the units to tenths, hundreds... // Perform the carry. for (int i(0); i < digit_count; ++i) { auto carry = digits[i] / 10; digits[i] = digits[i] % 10; if (i != digit_count - 1) { // Add the carry to the next digit. digits[i + 1] += carry; } else { // New leftmost digit(s). if (carry > 0) { int & remaining(carry); do { auto digit = remaining % 10; remaining /= 10; digits.push_back(digit); } while (remaining > 0); } } } } // Print out the digits. for (auto it = digits.rbegin(); it != digits.rend(); ++it) { cout << *it; } }
mailtokks290199 can you explain what is happening here
jtsaur [deleted]ken771209 great idea
ayushkr08 Awesome !! Blown my mind off !!
adityarock90317 Well anyone can explain me this code??
ayushkr08 I am not good at explaining, this guy is using very basic method of multiplication that we learnt as kid and he is storing each digit of ans in separate box in reverse order. he is following this tactic i.e 22*4 can be written as 2*4 , 2*4 then storing them in different indexs of
Octowl I thought this would be a cake walk. Just implement a tail recursive function and call it on N.
...then I realized I was trying to do this in JavaScript.
My function is fine. It works. The answers are right.
BUT THE TESTS FAIL because JS has precision limits and returns answers in Scientific Notation!
747fceb9f94e5db [deleted]McClainj It should be solvable in all languages even if it is more difficult for some.
dilantha_prasan1 why don't you just do it in c or c++ ? you have to implement big integers by your ownself....
Sandhiya95 Is there any datatype to store such huge numbers!!!!OMG!!!!!!!!!!!!!!!!!!!!!
nikhilksingh97 i did it by storing the factorial value digits in an array....and it simply works!!!!(no tension of data type limits....) :)
Sandhiya95 Ty!!That helped:)
etayluz int main(){ int n; scanf("%d",&n); int arr[1000] = {0}; arr[0] = 1; int len = 1; for (int i = 2; i <= n; i++) { int carry = 0; for (int j = 0; j < len; j++) { int mul = i * arr[j] + carry; int dig = mul % 10; arr[j] = dig; carry = mul / 10; } while (carry) { len++; int dig = carry % 10; arr[len - 1] = dig; carry /= 10; } } for (int i = len - 1; i >= 0; i--) { printf("%d", arr[i]); } return 0; }etayluz This algorithm works the way we learned how to do multiplication in 3rd grade, but using a super carry as opposed to a one digit carry. So instead of multiplying each digit of the first number by each digit of the second number, we multiply each digit of the first number by the entire second number. This resuls in a "super carry", a carry that could be greater than a two digit number. It took me a long while to get this though - if written in C or a language that doesn't support more than 64 bit multiplication - this question should be marked as hard.
eric_zhu5121 this naive super carrier added to next result could be so big over int limit, it's not practical in this question.
parzec Not really. I did the same approach in c++ and checked how large the "super carry" could get. When calculating 100! it never reaches 100, well in the limits of an int. Anyone curious or doubting can just copy the code above and add a few lines to check.
zaidrpm Question states: 1<=n<=100 So largest possible multiplication: 9*100 which is well under limit of int
vigneshkutta It would be better if you could explain with an example.
AndyS_12 Thnks for the super carry explanation!!.......I was stuck in that for quite long before reading discussion..
Rys23 well pretty much every problem here should be marked lower than currently is if you are using python or in some cases even any OOP language because you are just calling functions of that language that will solve the problem for you...
ganeshlandge936 Thanks for the nice explanation!!
khuatgia Hi Etayluz,
Thank you for your comment. May I ask a little about your solution ?
My solution is almost exactly the same, excep that in this while loop while (carry) { len++; int dig = carry % 10; arr[len - 1] = dig; carry /= 10; }
I did not have the step dig = carry % 10, and my answer was correct up to 15 !, but after that it was wrong. It worked for numbers even as big as 25 ! when I added the line dig = carry % 10. I really don't understand why because I wrote my program in C++ and even store everything in unsigned long, which gives me the maximum of bits I can think of..But yours seem to be written in C and you stored everything in int ? When I tried to store my variables in int, it did not give the correct answer. I would really appreciate if someone knows the answer why there is such a difference in result ! Thank you
Elbek Thanks for help!
nideeshmanian Fantastic. I got an idea, what u are doing. But the code bieng so simple and small. I amamazed at how you reach the solution. I could not decipher the code yet. I understood you were doing like we used to multply using paper and pencils. Kudos. All the best for your career.
Zodiac99 very good work. impressive...
dimahwang Wow!
agarwal_ankur09 def get_factorial2(n): old = [1] current = [] for i in xrange(2, n+1): carry = 0 for digit in old: prod = int(digit) * i + carry rem = prod % 10 current.append(rem) carry = prod / 10 if carry != 0: for j in str(carry)[::-1]: current.append(j) # add j as a str old = current current = [] return "".join(map(str,old[::-1])) # convert everything to str before concatenation and returning the results n = int(raw_input().strip()) print get_factorial2(n)
Here my python solution using super carry method. Exactly same as @etayluz's
chandan37shaw nice way to solve this one
ME_170070246 thank you for your help sir,because of you i got this code
[deleted] Very nice logic. I learned something new. Thank you Sir.
Rishab_Redhu [deleted]
player007 Thanks for the approach.
syamprasadkr @etayluz Thank you so much for the explanation!
bitralahari20171 i cant even think of solving it in c,its really invloves deep thinking to solve it.thats great of u....
kasam_balaji_141 Thanks Man yours is the simplest and concise solution here
krishna858606 how
sarangsbabu367 How??
shubham707007801 CAN U EXPLAIN THIS ???
sattujaiswal BigInteger in java
AshimGupta [deleted]AshimGupta [deleted]
shadowchi YES in java we have BigInteger
debottam_dd solution of this code in c...
int main() { int n, a[10000] = {0}, i = 0, carry, cpy, len, func, neww; scanf("%d", &n); if(n==1) printf("1"); else { cpy = n; while (cpy != 0) { a[i] = cpy % 10; cpy = cpy / 10; i++; } while (n != 1) { for (len = 0; len < i; len++); n--; i = 0; carry = 0; for (i = 0; i <= len + 1; i++) { func = n * a[i] + carry; a[i] = func % 10; carry = func / 10; } } for (i = len; i >= 0; i--) if (a[i] != 0) { neww = i; break; } for (i = neww; i >= 0; i--) printf("%d", a[i]); } }
logic : - suppose you're asked to multiply 25 with 24..
what toddlers do..
25* 24
100
50 *
600
what we do... 5*24=120, 0 stays, carry 12... then 2*24+12=60.. hence 600. this method is called supercarry. Take an array, use this supercarry method and for every i, print a digit in array[i]. then print the anti-array. If there are extra zeroes in front of the answer, remove them by using..
for (i = len; i >= 0; i--) if (a[i] != 0) { neww = i; break; } for (i = neww; i >= 0; i--) printf("%d", a[i]);how your multiplication goes..
n=25.
52 006 00831 006303
etc..
when you print the anti-array
the number prints without any problem...
praveenraj9495 Can you explain how i <= len + 1 is working correctly? When I try to multiply two numbers (1050 * 1049) using your code, it's producing wrong results, it's missing some digits.
But Factorial is working fine. Can you explain?
har33sh Its cakewalk if you know Python :P
itaravin Same cakewalk in Ruby too ;)
mahak1 Can you tell how you did it in py thon?
shashankkmr34 have u done it in c/c++?? if yes ,make me understand too in simple way
viigihabe Looked down at the link "Environment". C++ developers have Boost in their hands. So it boils down to:
#include <boost/multiprecision/cpp_int.hpp> // Complete the extraLongFactorials function below. void extraLongFactorials(int n) { using boost::multiprecision::cpp_int; int multiplier = 1; cpp_int factorial = 1; while(multiplier <= n) factorial *= multiplier++; cout << factorial; }
My comment doesn't have any algorithmical value but it might direct to right direction. Don't invent the wheel when someone has done it allready.
manushikapoor i have done the same but getting error that it does not exist.
ayushyadav96 import sys n = int(raw_input().strip()) def fact(n): if(n==1): return 1 prod=n*fact(n-1) return prod print fact(n)
Simply forget that n is big. It's python :)
anujoy You can achieve this in one line in python ->
print reduce(lambda x, y: x*y, range(n+1)[1:])
ghaniahsan please explain
tricerabottoms You can do it in one line:
print((1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600,6227020800,87178291200,1307674368000,20922789888000,355687428096000,6402373705728000,121645100408832000,2432902008176640000,51090942171709440000,1124000727777607680000,25852016738884976640000,620448401733239439360000,15511210043330985984000000,403291461126605635584000000,10888869450418352160768000000,304888344611713860501504000000,8841761993739701954543616000000,265252859812191058636308480000000,8222838654177922817725562880000000,263130836933693530167218012160000000,8683317618811886495518194401280000000,295232799039604140847618609643520000000,10333147966386144929666651337523200000000,371993326789901217467999448150835200000000,13763753091226345046315979581580902400000000,523022617466601111760007224100074291200000000,20397882081197443358640281739902897356800000000,815915283247897734345611269596115894272000000000,33452526613163807108170062053440751665152000000000,1405006117752879898543142606244511569936384000000000,60415263063373835637355132068513997507264512000000000,2658271574788448768043625811014615890319638528000000000,119622220865480194561963161495657715064383733760000000000,5502622159812088949850305428800254892961651752960000000000,258623241511168180642964355153611979969197632389120000000000,12413915592536072670862289047373375038521486354677760000000000,608281864034267560872252163321295376887552831379210240000000000,30414093201713378043612608166064768844377641568960512000000000000,1551118753287382280224243016469303211063259720016986112000000000000,80658175170943878571660636856403766975289505440883277824000000000000,4274883284060025564298013753389399649690343788366813724672000000000000,230843697339241380472092742683027581083278564571807941132288000000000000,12696403353658275925965100847566516959580321051449436762275840000000000000,710998587804863451854045647463724949736497978881168458687447040000000000000,40526919504877216755680601905432322134980384796226602145184481280000000000000,2350561331282878571829474910515074683828862318181142924420699914240000000000000,138683118545689835737939019720389406345902876772687432540821294940160000000000000,8320987112741390144276341183223364380754172606361245952449277696409600000000000000,507580213877224798800856812176625227226004528988036003099405939480985600000000000000,31469973260387937525653122354950764088012280797258232192163168247821107200000000000000,1982608315404440064116146708361898137544773690227268628106279599612729753600000000000000,126886932185884164103433389335161480802865516174545192198801894375214704230400000000000000,8247650592082470666723170306785496252186258551345437492922123134388955774976000000000000000,544344939077443064003729240247842752644293064388798874532860126869671081148416000000000000000,36471110918188685288249859096605464427167635314049524593701628500267962436943872000000000000000,2480035542436830599600990418569171581047399201355367672371710738018221445712183296000000000000000,171122452428141311372468338881272839092270544893520369393648040923257279754140647424000000000000000,11978571669969891796072783721689098736458938142546425857555362864628009582789845319680000000000000000,850478588567862317521167644239926010288584608120796235886430763388588680378079017697280000000000000000,61234458376886086861524070385274672740778091784697328983823014963978384987221689274204160000000000000000,4470115461512684340891257138125051110076800700282905015819080092370422104067183317016903680000000000000000,330788544151938641225953028221253782145683251820934971170611926835411235700971565459250872320000000000000000,24809140811395398091946477116594033660926243886570122837795894512655842677572867409443815424000000000000000000,1885494701666050254987932260861146558230394535379329335672487982961844043495537923117729972224000000000000000000,145183092028285869634070784086308284983740379224208358846781574688061991349156420080065207861248000000000000000000,11324281178206297831457521158732046228731749579488251990048962825668835325234200766245086213177344000000000000000000,894618213078297528685144171539831652069808216779571907213868063227837990693501860533361810841010176000000000000000000,71569457046263802294811533723186532165584657342365752577109445058227039255480148842668944867280814080000000000000000000,5797126020747367985879734231578109105412357244731625958745865049716390179693892056256184534249745940480000000000000000000,475364333701284174842138206989404946643813294067993328617160934076743994734899148613007131808479167119360000000000000000000,39455239697206586511897471180120610571436503407643446275224357528369751562996629334879591940103770870906880000000000000000000,3314240134565353266999387579130131288000666286242049487118846032383059131291716864129885722968716753156177920000000000000000000,281710411438055027694947944226061159480056634330574206405101912752560026159795933451040286452340924018275123200000000000000000000,24227095383672732381765523203441259715284870552429381750838764496720162249742450276789464634901319465571660595200000000000000000000,2107757298379527717213600518699389595229783738061356212322972511214654115727593174080683423236414793504734471782400000000000000000000,185482642257398439114796845645546284380220968949399346684421580986889562184028199319100141244804501828416633516851200000000000000000000,16507955160908461081216919262453619309839666236496541854913520707833171034378509739399912570787600662729080382999756800000000000000000000,1485715964481761497309522733620825737885569961284688766942216863704985393094065876545992131370884059645617234469978112000000000000000000000,135200152767840296255166568759495142147586866476906677791741734597153670771559994765685283954750449427751168336768008192000000000000000000000,12438414054641307255475324325873553077577991715875414356840239582938137710983519518443046123837041347353107486982656753664000000000000000000000,1156772507081641574759205162306240436214753229576413535186142281213246807121467315215203289516844845303838996289387078090752000000000000000000000,108736615665674308027365285256786601004186803580182872307497374434045199869417927630229109214583415458560865651202385340530688000000000000000000000,10329978488239059262599702099394727095397746340117372869212250571234293987594703124871765375385424468563282236864226607350415360000000000000000000000,991677934870949689209571401541893801158183648651267795444376054838492222809091499987689476037000748982075094738965754305639874560000000000000000000000,96192759682482119853328425949563698712343813919172976158104477319333745612481875498805879175589072651261284189679678167647067832320000000000000000000000,9426890448883247745626185743057242473809693764078951663494238777294707070023223798882976159207729119823605850588608460429412647567360000000000000000000000,933262154439441526816992388562667004907159682643816214685929638952175999932299156089414639761565182862536979208272237582511852109168640000000000000000000000,93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000)[int(input())])
sliu8 Stupidest way to solve a problem
tricerabottoms I simplify for your benefit, my friend. Here is the full version:
from math import factorial eval('print(({})[int(input())])'.format(','.join([str(factorial(i)) for i in range(101)])))
funkeey you're the best 😂😂😂
tixaxehew Well placed humor, worth the effort!
marcphilippebea1 You win...
Wasim_AbbaCi hats off! Mr.Optimized!
yahyouch36 well , that's not one line .
chuppi_angadi print(math.factorial(n))
mohanprasath468 print(math.factorial(n)
vd85321 No more than 3 lines of code to solve this in C#.
tedbreen I solved this with JavaScript by converting my numbers to strings first and performing bit by bit calculations.
CrabDude But that's half the fun! Here's my JavaScript solution:
function main() { var n = parseInt(readLine()); let sum = [1] // Length is half max length b/c we're multiplying const MAX_LENGTH = Math.floor(String(Number.MAX_SAFE_INTEGER).length/2)-1 const MAX_VALUE = Number(Array(MAX_LENGTH+1).join('9')) for (let i=2; i<=n; i++) { let carryover = 0 for (let j=0; j<sum.length; j++) { let newValue = sum[j] * i + carryover if (newValue > MAX_VALUE) { let newValueStr = String(newValue) carryover = Number(newValueStr.substr(0, newValueStr.length-MAX_LENGTH)) sum[j] = Number(newValueStr.substr(-MAX_LENGTH)) } else { carryover = 0 sum[j] = newValue } } if (carryover !== 0) sum.push(carryover) } // Don't left-pad the highest order group let highestGroup = sum.pop() // Left pad all other groups with '0' sum = sum.map(v=>Array(MAX_LENGTH+1-String(v).length).join('0')+v) console.log(highestGroup + sum.reverse().join('')) }
nikolay_golubov I tired to solve this f***g problem, i terminated due to timeout or memory overflow for n > 60, but my code must be a correct. Your code works fine, nice job.
jorgeh_work On the hackerrank's Environment page mentions that HR supports bignumber.js library for javascript. You have to add a require statement for using it. bn = require('bignumber.js');
vernonquan ^ This
Here's my iterative solution using bignumber.js
const bigFactorial = n => { const bigNumber = require('bignumber.js'); let result = new bigNumber(1); for (let i = 1; i <= n; i++) { result = result.mul(i); } return result.toFixed(); } console.log(bigFactorial(n));
adamxtokyo ^ This info should be given in the problem description imo.
I'm surprised at how bad the problem descriptions are here sometimes. I've failed tests so many times because the description was unclear or didn't mention certain restrictions etc. Also, why aren't all tests free to see? (ノಠ益ಠ)ノ彡┻━┻
Sorry, I digress... Rant over.
Here's my oneliner solution to the problem in JavaScript (using recursion):
const BigNumber = require('bignumber.js') const extraLongFactorials = (n, f = new BigNumber(1)) => n === 1 ? console.log(f.toFixed()) : extraLongFactorials(n - 1, f.times(n))
malaschitz_m I used BigInt. You do not have use require or import. But you cannot mix BigInt and Number.
blackjar72 Why would you use recursion? An iterative approach is so easy and more efficient?
tricerabottoms Fun facts:
a = 9007199254740992; console.log(a == a); console.log(a + 1 == a); console.log(a + 1 + 1 == a); console.log(a + (1 + 1 + 1 + 1) == a + 5);
CristianNaziru lol
ronald_gayda_13 Can use BigInt now
santiago_degetau Use
BigInt();Check it out at MDN BigIntArthurSerafim Hey bro, I believe you didn't have this feature 4 years ago, but now we can do that in JS!
function extraLongFactorials(n) { n = BigInt(n) var accumulator = BigInt(1); for (let i = n; i > 0; i--) { accumulator = accumulator * i } console.log(accumulator.toString()) }
samueljseay You can do it with JavaScript's BigInt to get correct precision.
k3csk3s just use BigInt
GabeKagan This is hilariously trivial in Ruby, which automatically creates big integers (Bignum) as needed. I should probably try it in a language that doesn't one of these days.
dheeraj I know. Try it in c, c++
roryneil Python as well. Sum = n = input. while n > 1, decrement n and sum *= n, print sum, 5 lines.
I think you're right, this is almost cheating in these languages.
zastari from math import factorial
crypter_dine Can u please explain Hoe to do this...
twinkle123 import math print math.factorial(n)
P1zzAdr0hn3 def printfactorial(n): ausgabe = n for q in range(1, n): ausgabe *= (n - q) return print(ausgabe)
crypter_dine Thanks a Lot.......I got cleared.
dingo_custer print reduce(lambda x,y: x*y,xrange(2,long(raw_input().strip())+1))
Ehouarn Another reason why I love (and sometimes hate) so much Ruby =]
nothlione Yeah, I did that in Python first, wrote two lines of code. Felt like cheating, haha.
tao_zhang Mine in Java
import java.io.*; import java.util.*; import java.math.*; public class Solution { public static void main(String[] args) { int n = (new Scanner(System.in)).nextInt(); BigInteger factorial = new BigInteger("1"); while (n>1){ factorial = factorial.multiply(BigInteger.valueOf(n)); n--; } System.out.println(factorial); } }
xinchen112 hello, I use java and try to solve it using a recursive method
public static void main(String[] args) { // TODO code application logic here Scanner in = new Scanner(System.in); int N = in.nextInt(); System.out.println(factorial(N)); } public static long factorial(int n){ if(n<0) return -1; else if(n==0) return 1; else return (long) n*factorial(n-1); }
the result is not correct, but I can't find the reason. Please help.
cesaregb withouth trying the code, I notice that you are using "long" vars, the problem mention that some of the number cannot be stored in a long (ie 64 bit type). Probably with a BigInteger can work.
xinchen112 Yes,you are right! Thank you!
jkamyabi Obviously it's a recursive solution, but the problem is much bigger than it. You have to calculate factorial using manually implemented data types.
Oarr2 it only works with n=1,2,....,19. The statement asks you to calculate 0<=n<=100. with a big n the answer of your code is negative because it overflows.
psprachi955 [deleted]
sourav47 can i find a factorial of 100 in java using BigInteger.if yes then respond me if no then Y?
sudmong You can improve the speed of this by keeping the calcuated factorials and using them in next iteration instead of calcualting it again.
Kulkarni Succint and simple. Good one.
Sort 720 Discussions, By:
Please Login in order to post a comment