Name | Code | Successful Submission | Accuracy |
---|---|---|---|

ZACKHAN | 1510 | 67.83 | |

HMAPPY2 | 1111 | 24.7 | |

CHEFSQRS | 757 | 46.95 | |

CHEFPRMS | 609 | 62.15 | |

FIBEASY | 428 | 21.38 | |

CHEFADV | 406 | 33.51 | |

KPRIME | 379 | 35.93 | |

BINXOR | 157 | 25 | |

CBALLS | 130 | 19.92 | |

CHMOD | 92 | 16.4 | |

EARTSEQ | 64 | 18.1 |

#### About the contest

- This contest is part of DSA Learning Series
- Topics of the contest: LogN GCD(Euclidean algorithm), Sqrt(n) factorisation, Sieve of Eratosthenes, prime factorisation, modular arithmetic and binary exponentiation
- Pre-requisite of the contest: None
- Follow the discussions around the contest by joining the group here: https://discuss.codechef.com/g/CodeChef-DSA-Learners-Group

#### Resources

**GCD **

- Definition: Greatest common divisor
- Basic brute force approach:
- To find GCD(a,b), go through all factors of one number and check if they are a factor of the other number.
- Time complexity: O(min(a,b))
- Space complexity: O(1)

- To find GCD(a,b), go through all factors of one number and check if they are a factor of the other number.
- Euclidean algorithm:
- Algorithm without proof (video): Euclid's algorithm made easy
- Algorithm with implementation: Euclidean algorithms (Basic and Extended)
- Algorithm with proof(text): The Euclidean Algorithm (article)
- TIme complexity proof: https://qr.ae/pNrZW1

- Libraries in languages which computes gcd

**Sqrt(n) factorisation**

- Basic brute force approach:
- To find all the factors of a given number N, we can iterate from 1 till N and check if they divide N or not.
- Time complexity: O(N)
- Space complexity: O(1) {if you are not storing factors}

- Basic run-through of the process: Finding factors of a number (video)

- To find all the factors of a given number N, we can iterate from 1 till N and check if they divide N or not.
- Sqrt(n) factorisation:
- To find all the factors of a given number
**N**, then we need to find all**a,b**such that**a*b=N.** - If we notice carefully, min(a,b)<=sqrt(n). But why?
- Let's assume min(a,b)>sqrt(n). This implies,
- a>sqrt(n)
- b>sqrt(n)
- a*b > n [this holds for all positive a & b]

- We have reached a contradiction because of a*b>n, therefore min(a,b)<=sqrt(n).
- Since we know min(a,b)<=sqrt(n) we can simply iterate from 1 till sqrt(n) and find all the factors.

- To find all the factors of a given number

**Sieve of Eratosthenes**

- Algorithm Visualisation: Sieve of Eratosthenes (video)
- Algorithm + Implementation: Sieve of Eratosthenes
- Prime factorisation using sieve: Prime Factorization using Sieve O(log n) for multiple queries

**Modular arithmetic**

- Introduction: Modular Arithmetic
- Modular Multiplicative inverse:
- When the mod is prime: Fermat's little theorem
- Using extended Euclidean algorithm(when mod and base are coprime): Modular multiplicative inverse

**Fast exponentiation**

- Binary exponentiation - Algorithm + Implementation : Binary Exponentiation
- Divide and conquer exponentiation - Algorithm + Implementation:A tutorial on Fast Modulo Multiplication (Exponential Squaring)

**Official Hints to the Contest Problems**

### Announcements

**Live Learning session for Contest 5 details announced here:**https://discuss.codechef.com/t/official-live-dsa-learning-session-6-contest-5/65630

In case you miss the live session find the recoding link on the discuss post in the previous link.

**Official Hints to the Contest Problems added**

**Please note:**

- The comments on the problem pages in this contest are not being moderated. Kindly ask your doubts in the discussion forum here: https://discuss.codechef.com/c/CodeChef-DSA-learners/68.
- Also, the problems that you solve in this contest is not reflected in your user profile because it is an ongoing contest.