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
washimdas2013 [deleted]
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
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
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.
steven_gerazdnn1 That's so true. I can understand the reason why basketball legends
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.
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
thetresspass6 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!
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.
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:])
joefu import math print math.factorial(int(raw_input()))
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...
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))
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
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!
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.
dheerajHackerRank Admin 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.
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.
whuang For those of you interested in challenging yourself to write this in C
#include <math.h> #include <stdio.h> #include <string.h> #include <stdlib.h> #include <assert.h> #include <limits.h> #include <stdbool.h> int main(){ int n, length_digit = 1; scanf("%d",&n); int *r = malloc(60 * sizeof(int)); r[0] = 1; for (int factor = 2; factor <= n; factor++) { int *carry = malloc( (length_digit + 2) * sizeof(int)); // first, evaluate product for (int i = 0; i < length_digit; i++) { r[i] *= factor; r[i] += carry[i]; if (r[i] / 100 > 0) { carry[i + 2] += r[i] / 100; carry[i + 1] += (r[i] % 100) / 10; r[i] = r[i] % 10; } else if (r[i] / 10 > 0) { carry[i + 1] += r[i] / 10; r[i] = r[i] % 10; } } // second, consider if length of digit increases if (carry[length_digit + 1] > 0) { r[length_digit + 1] = carry[length_digit + 1]; r[length_digit + 1] += carry[length_digit] / 10; r[length_digit] = carry[length_digit] % 10; length_digit += 2; } else if (carry[length_digit] > 0) { r[length_digit] = carry[length_digit]; length_digit++; } } // print for(int i = length_digit - 1; i >= 0; i--){ printf("%d", r[i]); } }
Madhurachanna This is my c++ program
void extraLongFactorials(int n) { int num; num = n; int len,carry,realnum,newnum,c; deque<int> a ; deque<int> temp; a.push_back(num); for (int i = 2; i < num ; i++) { len = a.size(); temp.clear(); carry = 0; for (int j = len-1; j >= 0 ; j--) { newnum = carry + (i * a[j]); temp.push_front(newnum % 10); carry = newnum / 10; } if (carry!=0) { while (carry!=0) { temp.push_front(carry%10); carry /= 10; } } a.clear(); a = temp; } for (int i = 0; i < a.size() ; i++) { cout << a[i] ; } }
martostef Best solution in C++
RodneyShag Java solution - passes 100% of test cases
From my HackerRank solutions.
import java.util.Scanner; import java.math.BigInteger; public class Solution { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int n = scan.nextInt(); scan.close(); System.out.println(factorial(n)); } private static BigInteger factorial(int n) { BigInteger result = BigInteger.ONE; while (n > 1) { result = result.multiply(BigInteger.valueOf(n)); n--; } return result; } }
Let me know if you have any questions.
hasilsharma7 A generic approach using linked list : https://github.com/Hasil-Sharma/Hackerrank/blob/master/ExtraLongFactorials.c
tchalvak Are factorials larger than 20, 25 even possible in php? Usually in php to handle this you'd have to install an extension, but that's not really an option for hackerrank, I expect.
RryLee Right..gmp extension
shahumangr Try bcmul() function of the BCMath extension. It seems to be working.
Sort 456 Discussions, By:
Please Login in order to post a comment