CPP notes

  Firstly, read the question carefully.  If able to understand 100% => don't read the test case else read the test cases to get the feel If not able to come up with any approach --> think of brute force -> then optimize Categorize the problem where it lies Brute Force Maths Binary Search  Greedy DP Graph Bitwise stuffs If given tree --> Visualize as shown in image (Think of BFS/DFS) If given subarray -> can think of prefix sum or dp If the code seems too lengthy => simplify => There must be a way Can use MATHS sometimes to simplify the expression or logic If dp => lookout for the transition and state definition first Whenever including edge case in anywhere always be 100% sure (even though you think its correct, it may be wrong). Lookout for edge cases !!! If sure of solution => spend time on edge cases, even it seems trivial If stuck  Check for negation of problem demand what will happen if include one by one  solve for small values l...

Binary Exponentiation - to find   a b  →  converted b into binary  Benefit - instead of multiplying b times => multiply   lo g 2 ( b ) times If a is large  →  take  (a % M) If M is itself very large (like 1e18) =>  instead of a*a  →  DO a+a+a....(a times) even if a*a = 1e18  →  will not get reduced log²(n) bcz log(n) for binary_Multiply & log(n) f or expo Same code as expo => Only change * to + everywhere If b is large in a b  →  a b c  ≠  a ( b c  %  M )  ( mod M )  →   cannot take mod in power Use Euler Theorem  →  a b c ≡ a ( b c  % ɸ(m) )  (mod M )  → ɸ is euler totient function For safety, add extra ɸ in power bcz above fails if gcd(a, m) ≠  1 a b c ≡ a (ɸ(m) + ( b c  % ɸ(m) )) ( mod M )   →  updated GCD + prime  properties a divides b + b divides a ---> a =  ±  b gcd is alwa...