Posts

Dynamic Memory Allocation + Pointers

Pointers -  stores address of variable int *a = &b --> a is pointer pointing to address of b --> use *a to access b int &a = b --> a is alias to b --> both a and b have same address => use a to access b arr [ 3 ] = { 5 , 10 , 20 }; *arr --> 5 but *(arr + 1) --> 10 for 2-D array -> *(*arr + 1) --> arr[0][1] and *(*(arr + 1)) --> arr[1][0] Dereferencing - Retrieve data contained at memory location where the pointer points void pointers give great flexibility as can point to any data type. But to dereference => first transform it into some other data type Memory Leak -  When user forgets to deallocate memory for future use m = malloc ( 5 ); m = NULL ;  →  allocate 5-byte memory from heap and store address in pointer m  → but now  program has lost this address bcz no pointer points to it anymore  →  this memory can't be accessed or freed for lifetime of program Dangling Pointer  - When delete pt...
Post a Comment
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...
Post a Comment
Read more

Sorting Algorithms

Image
Some Terms In-place Sorting => use constant space to sort (modify only the given array) Stable sorting - When two same values appear in the same relative order in sorted data as in the original array => Eg: Merge Sort, Insertion Sort, Bubble Sort ₪ When equal elements are indistinguishable like integers => stability is not an issue.         →    ----> If stable sorting is used => get shown pic ₪   If we sort section-wise & sorting algorithm is unstable => may get random ordering ₪  Any given sorting algorithm which is unstable can be modified to be stable     Augment index along with value → If values are same  → use index as tiebreaker → Drawback - extra O(N) space to store index for N element + need extra comparison Counting sort is unstable but can be made stable - 1 6a 8 3 6b 0 6c 4 ---> a, b, c is used just to distinguish ordering of same value Stable Algo - 0 1 3 4 6a 6b 6c 8 count arr...
Post a Comment
Read more

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
Post a Comment
Read more

How to Approach problem ??

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