Gcd2 algorithm

someone please help me understand the GCD2 problem in the practice (easy) section of codechef and please explain the solution ,i am not able to solve this problem …please help .

Scan the variable B as a string find mod of the numeric string with A
sum = 0
Loop(I,B.length()){

sum = (sum*10 + B[i]-‘a’)%A
}

Print(GCD(A,SUM))

1 Like


See this

1 Like

can you please explain the purpose of line sum=(sum+B[i]-‘a’)%A .

In the question , as you can see B is a very large integer , so you have to input it as a string . Now in
that line he is just changing string to integer , you can also write it as sum = (sum*10) + B[i] - ‘0’;
Now you are thinking why (%A). Because whenever B becomes larger than A it will decrease it and make it smaller than itself. NOW you must be thinking , Why it will not affect the result , because in GCD we take the mod of the greater number/ smaller number.So, the answer won’t get affected.

nicely explained the solution …i understood the solution .keep doing this good work.

@riddle279 to better understand this type of question (like Modular arithmetic) –
see my articles on geeksforgeeks

  1. Count all prefixes of the given binary array which are divisible by x
  2. Length of the smallest number which is divisible by K and formed by using 1’s only