How to Approach problem ??

  1.  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
  2. If not able to come up with any approach --> think of brute force -> then optimize
  3. Categorize the problem where it lies
    • Brute Force
    • Maths
    • Binary Search 
    • Greedy
    • DP
    • Graph
    • Bitwise stuffs

  4. If given tree --> Visualize as shown in image (Think of BFS/DFS)
  5. If given subarray -> can think of prefix sum or dp

  6. If the code seems too lengthy => simplify => There must be a way
    • Can use MATHS sometimes to simplify the expression or logic

  7. If dp => lookout for the transition and state definition first
  8. Whenever including edge case in anywhere always be 100% sure (even though you think its correct, it may be wrong).
  9. Lookout for edge cases !!!
    • If sure of solution => spend time on edge cases, even it seems trivial

  10. If stuck 
    • Check for negation of problem demand
    • what will happen if include one by one 
    • solve for small values
    • look for trend and the overlapping portions (if TLE)

  11. Try to simplify problem statement (if feels complex)
  12. If remove subarray -> can use prefix + suffix array combination
  13. If hard to find for equality --> find for inequality and adjust
    • Example - Find no. of subarray whose product = k → let's say it's easy to find no. of subarray whose product ≤ k → ans = fun(k) - fun(k-1)

Comments

Post a Comment

Popular posts from this blog

Templates (for CP)

Next smaller element in left and right side of any element -  Link     (Can easily modify) Next greater element for both sides in one pass -  Link String Hashing -  Link MUST call precalc() inside function Count inversions in any random array (GENERAL)  -  Link Count inversions in binary string -  Link Sum of XOR of all subarrays -  Link  ——₪——  Original question link Sum of XOR of all subsequence -   Link  ——₪——  Original question link Prefix sum of 2-D array -  Link Number of subarrays with sum = k →  Link Number of subarrays with sum divisible by k  →  Link Segment Trees →  Link djikstera algorithm -  Link Prime Factorization of given number n →  Link Count no. of divisors in  O(N ⅓ )  →  Link
Read more

DSA Trees + Heap

Image
Trees are special form of graph If n nodes => n-1 edges (means 2 points have only 1 line joining them) They are acyclic => means from node A to node B there is only 1 way to reach Whenever see  stuffs like  connected ,  unique path  -> tree Types of traversal in trees inorder traversion - left -> root -> right preorder traversion - root -> left  -> right postorder traversion - left  -> right -> root If first time visited -> must be root (bcz parent hai)  => PRE-ORDER If second time visited -> left subtree fully analyzed bcz we are moving in anti-clockwise direction => toh left check krke hi aayenge  => IN-ORDER If third time visited -> left and right subtree fully analyzed => POST-ORDER Post-order is reverse of Pre-order from clockwise Binary search tree (BST) = Binary tree + Search property each subtree follows -- left subtree < root value < right subtree Inorder traversal in BST is...
Read more

Modular Basics + Number Theory + Permutations

Image
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...
Read more