- Practice
- Functional Programming
- Ad Hoc
- Huge GCD
- Discussions

# Huge GCD

# Huge GCD

jarmex + 0 comments it is really easy to use the bigint structure (F#)

ismailmarmoush + 1 comment What does this part mean

`But instead of printing complete answer you have to print answer modulo 109+7.`

Also the explaination of test case 2 is not related to how actually the method should be solved, there would be no way of discovering such pattern of 2^a and 3^a

abhiranjan + 2 comments Hi, as the output can be very large (exceeding the limits of 64 bits integer) modulo operation common way to check the correctness of output.

It is only a explanation that first series is power of two, while second is power of three. You don't have to find such patter.

dolgov_vv + 2 comments The task is not about Functional Programming. It's a pure Number theory.

abhiranjan + 1 comment Yep, that's why it's placed in MISC chapter :)

Jonnymoo + 0 comments You wouldn't happen to have a handy link the number theory side of it would you?

carl_smotricz + 0 comments It's possible to fiddle with lists of factors to keep numbers small, and that would be Number Theory.

But it's also possible to do what I did and use some implementation of Big Integers to actually simply multiply those numbers out, find their GCD, modulo it to 1000000007 and print it out.

julius_angres + 0 comments One-liner in Haskell (no focus on performance though):

`solve :: [Integer] -> [Integer] -> Integer solve ns ms = flip mod (10^9 + 7) $ gcd (product ns) (product ms)`

weozUA + 0 comments Scala solution:

import scala.io.StdIn object Solution extends App { def gcd(x: BigInt, y: BigInt): BigInt = { if (x == 0) y else gcd(y % x, x) } def product(nums: String): BigInt = { nums.split(" ").map(BigInt(_)).product } val f = () => StdIn.readLine() val (_, a, _, b) = (f(), product(f()), f(), product(f())) println(gcd(a, b) % 1000000007) }

pabiagioli + 1 comment My OCaml code works fine with the first 3 TC, but on #3 it starts to break... First I get a list of prime factors, I generate a Set of factors and intersect them with each other so the (Prime, Exponent) lists can have the same length and items. Then I count each number in the common set and make a List of (Prime, Exponent). Last, I get the least Exponent and multiply to get the total number and apply the modulo operation.

The result given in the output is a negative number, so I guess I ran out of Int64 values while multiplying...

I'm running into a lot of timeout/memory issues with these kinds of exercises and OCaml, should I be using another language?

pabiagioli + 0 comments I fixed my issue with the Int64 overflow. It's funny because I couldn't use the (**) operator.

Thanks anyway

mukeshsinghbhak1 + 0 comments main = do n <- getLine str1 <- getLine m <- getLine str2 <- getLine let x = show $ process str1 str2 putStrLn x

process ab cd = compute (product words ab) (product words cd) compute a b = mod (gcd1 a b) 1000000007

allDivisors n = [x | x <- [1..n] , mod n x == 0] gcd1 a 0 = a gcd1 0 b = b gcd1 a b = maximum $ map maximum [[x,y] | x <- allDivisors a, y <- allDivisors b , x==y ]

whats wrong with my code

CKoenig + 2 comments it's IMO to simple if you cheat by taking advantage of bigints - but hey I guess it's the Hacker way

blubberdiblub + 0 comments Well, I think it just shows that there didn't go a lot of thought into designing the problem.

Elmex90s + 0 comments I think they should make a version where they prohibit the use of big integers like Integer in Haskell. It is also worth mentioning there is a solution without factorizing integers to prime powers like in the official editorial solution. If you do it this way you really have a great problem + solution. Despite that, a solution in Python or C would be much easier to program.

amanjaiswal + 1 comment what is wrong with this code .... this code is working fine on my Terminal ...

hugeGcd nListInt mListInt = gcd (product nListInt) (product mListInt) main :: IO () main = do n <- getLine nList <- getLine let nListInt = map read $ words nList :: [Int] m <- getLine mList <- getLine let mListInt = map read $ words mList :: [Int] putStrLn $ show (hugeGcd nListInt mListInt)

CKoenig + 1 comment `product nListInt`

will overflow - for example`product [1..100 :: Int]`

will evaluate to 0 - just add in`fromIntegral`

or change`Int`

to`Integer`

and you are good to goamanjaiswal + 1 comment why this happen can you please explane this

CKoenig + 1 comment ok I'll try - see Int has usually 64bits - but let's make things easier and assume that we have only 4bits - one of these indicates positive or negative so we have 3bits for positive left

Now when you do 1(=001)*2(=010)*3(=011)*4(=100) you already are at 24(=11000) and as you can see this is more that fits the 4 bits (the same is true for 64bits - it just takes more factors)

if you get no overflow protection the higher bits are just truncated (and you will shift out all 1s and end up as GHCi tells you with 0).

On the other hand, if there is protection enabled you get an exception - in both cases you end up with a wrong program

if you switch to Integer the numbers can grow as big as you've got memory for your program (more than enough for this case) and so you don't run into overflows or exceptions here.

amanjaiswal + 0 comments WOw , Thanks for this greate and wonderful explanation thanks a lot

Raleigh_Foster + 1 comment I'm getting an error on the third practice case when using "List.map int_of_string (Str.split (Str.regexp " ") (read_line()))". The error is an int_of_string error. I also get an error on the very last (hidden) test case. Everything else works and I just use the Big_int module so there shouldn't be any sneaky errors implementing Big_int.

Is it possible that the input is bugged? (say delimited by a tab somewhere or something?)

glionnet + 1 comment I know your message is verry old but I get the same error, it seems that some of the line end with \r\n instead of \n.

shashank21jHackerRank Admin + 1 comment in which test case number?

glionnet + 0 comments Ok, it seems the issue is a little bit deeper, it always happen at the last test-case of a series of test-case. That means :

`- at "Test Case #2" during simple run - at "Test Case #14" during submissions`

Sort 11 Discussions, By:

Please Login in order to post a comment