# Connecting Towns

# Connecting Towns

stzsch + 2 comments Pretty annoying, not really a mathematics challenge, but rather a "know-how-to-deal-with-long-integers" challenge.

mike006322 + 4 comments The way modular arithmatic works, you can take the mod of each component of the product before you calculate the product and get the same result as if you were to mod the poduct after multiplying. My code had something like:

int product = 1 for (i<n-1) { product = product*T[i]%1234567 }

jeremydcarr + 0 comments Thanks for that explanation. I was wondering why my solution of doing it after the multiplication was not working. I figured it was overflow causing issues, but I didn't think to solve that like this.

jongod5399 + 0 comments [deleted]maheshvangala191 + 1 comment why 1234567 why not the other number be taken?

mike006322 + 1 comment "Output Format Total number of routes from T1 to Tn modulo

**1234567**"The problem says to output mod 1234567. That is where that number comes from.

SL170040679 + 1 comment but he didnt clearly mention that we have to take mod of each value

mukesh61 + 1 comment taking mod at each value helps in keeping the product in the range of 1234567 so computation will be easy. concept is (a*b*c) mod 1234567== (a mod 1234567) * (b mod 1234567) * (c mod 1234567)

SL170040679 + 0 comments okay..thanks

piyush1751995 + 1 comment shouldn't there be product = product%123456 after the loop.

I have studied (A * B) mod C = (A mod C * B mod C)

**mod C**syockit + 0 comments It's because in this case you know B is already mod C, so you calculate (A mod C * B) mod C. In fact, mike's code started with 1, so it's actually ((1 * A) mod C * B) mod C

carylouder007 + 0 comments i like the post, thanks for href test click here to go

[url=https://www.google.com/] click to go [/url]

www.google.com

i like the post, thanks for sharing..

cfranco + 0 comments If you're failing all but 1 of the test cases, you more than likely did not implement the modulo described in the instructions. In my opinion this problem would be much better if we didn't have to handle data overflow in such a way. In any case it's only 1 extra line of code:

var routeCount=1; for(int i=0;i<routes.Length;i++){ routeCount*=routes[i]; routeCount%=1234567; } return routeCount;

nilkun + 2 comments Snippet.

for(int j = 0; j < towns - 1; j++) { routes *= scanner.nextInt(); for(;;) { if (routes > 1234567) routes = routes - 1234567; else break; } }

Marcinho + 0 comments Awesome solution! Thank you :)

piyush1751995 + 0 comments take remainder directly

ROCKET_RONALDO + 1 comment easy question

#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> using namespace std; int main() { int t; cin>>t; while(t--) { int n; cin>>n; long long sum=1; for(int i=0;i<n-1;i++) { long long x; cin>>x; sum=((sum%1234567)*(x%1234567))%1234567; } cout<<sum<<endl; } return 0; }

gbekosa + 1 comment Why are you using mod 1234567 3 times? You only need to use it once after multiplying sum by x.

sum = (sum * x) % 1234567;

Learner_College + 1 comment BCoz it is a modulo property. (a*b)%c=((a%c)*(b%c))%c

AdarkTheCodr + 1 comment That is the property, yes, but you can remove the first two modulos because a)

`x`

is between 1 and 1000, so`x modulo 1234567`

is pointless, and b) modulo-ing`sum`

before it is used in the equation*and*before assigning the result back to`sum`

is redundant.Freiling + 0 comments You are correct, but best practice may be to assume that inputs will not always be under 1000. Even though it says so in the question, it reduces future maintenance in a hypothetical.

Freiling + 0 comments The modulo makes me laugh a bit... they have this story layer with Gandalf traveling between towns to make the question make sense. Then, with no explanation, the answer must be submitted as a modulo.

You weird, Gandalf.

c650Alpha + 0 comments Those were some biga$$ numbers.

ankitarun + 4 comments while multiplying all the elements in a list and printing the output, how is

for i in list: ans *= i print (int(fmod(ans,1234567)))

and

print (functools.reduce(op.mul, s, 1) % 1234567)

different. As, in one case solution is being accepted while in another it just passes only one testcase.

manvee_2603 + 1 comment why we are using mod1234567

RSTHW + 0 comments read format output again

manvee_2603 + 0 comments why we are using mod1234567

johnlr + 0 comments `fmod`

returns a float, so you will print extra`.0`

on each termquick_dudley + 0 comments Forgetting to output mod some number is the #1 mistake I make on hackerrank problems.

aryangarg1999 + 0 comments def connectingTowns(n, routes):

`prod = 1 for i in routes: prod *= i return prod%1234567`

PY_Berrard + 0 comments Haskell implementation using a fold

solve :: [Int] -> Int solve = foldl1 (\m n -> m * n `mod` 1234567)

Sort 88 Discussions, By:

Please Login in order to post a comment