Posts

Dynamic Memory Allocation + Pointers

Pointers Pointer — stores the address of a variable int *a = &b → a is a pointer to the address of b → use *a to access b int &a = b → a is alias (reference) to b → both share the same address → use a to access b arr [ 3 ] = { 5 , 10 , 20 }; // *arr → 5 // *(arr + 1) → 10 // For 2-D array: *(*arr + 1) → arr[0][1] *(*(arr + 1)) → arr[1][0] Dereferencing Retrieve the data stored at the memory location a pointer points to. Void pointers give great flexibility — they can point to any data type. But to dereference → first cast it to a concrete data type. Memory Leak When a program forgets to deallocate memory, making it unavailable for future use. m = malloc ( 5 ); m = NULL ; // Allocates 5 bytes on heap → stores address in pointer m // Sets m = NULL → program loses that address // No pointer refers to that memory anymore // → Cannot be accessed or freed for the lifetime of the program Dangling Pointer d...
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