Author: devangini123

🌙 What is a Fibonacci Number? The Fibonacci sequence is a famous mathematical series in which each number is the sum of two preceding ones It’s defined by the recurrence relation: F(0) = 0 F(1) = 1 F(n) = F(n-1) + F(n-2) for n > 1 This generates a series like: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, … Each number is the sum of the two before it. This sequence appears frequently in nature (e.g., flower petals, pine cones, and spiral shells), in algorithms (like dynamic programming), and even in computer science problems related to recursion,…

🌙 Problem Statement: Write a recursive function isPowerOfTwo(n) that returns true if n is a power of 2, otherwise false. Example 1: Input: 8 Process: (8 → 4 → 2 → 1) Output: true Example 2: Input: 18 Output: false Concepts: Power of Two: A number is a power of 2 if it can be divided by 2 repeatedly until it reaches 1. Base Case: n == 1 → true Invalid Case: n < 1 or n % 2 != 0 → false Recursive Case: isPowerOfTwo(n / 2) Time & Space Complexity: Time Complexity: O(log n) Space Complexity: O(log n)…

🌙 Problem Statement: Write a recursive function fact(n) that returns the factorial of a number n. Example: Input: 5 Process: (5 * 4 * 3 * 2 * 1) Output: 120 Concepts: Recursion: Repeatedly multiply n with fact (n-1). Base Case: fact(1) = 1. Recursive Case: n * fact(n – 1) Approach: If n == 1, return 1 (base case). Else, return n * fact(n – 1). Time & Space Complexity: Time Complexity: O(n) Space Complexity: O(n) recursive call stack JavaScript Python Java C++ C C# using System; class Program { static int Fact(int n) { if (n == 1)…

🌙 Problem Statement: Write a recursive function sum(n) that calculates the sum of all odd numbers in an array arr up to index n. Example: Input: [5, 2, 6, 1, 3] Odd Numbers: 5, 1, 3 Output: 9 Concepts: Recursion: Repeatedly check whether arr[n] is odd, and add it only if true true. Base Case: If n == 0, return arr[0] if it’s odd, otherwise 0. Recursive Case: Return (arr[n] if odd) + sum(n – 1). Approach: Check if arr[n] is odd. If yes, add it to recursive result of sum(n-1). Else, skip it and continue recursion. Time & Space…

🌙 Problem Statement: Write a function sum(n) that calculates the sum of all numbers in an array arr using recursion. It sums from index 0 to n. Example: Input: [5, 2, 6, 1, 3] Process: 5 + 2 + 6 + 1 + 3 = 17 Output: 17 Concepts: Recursion: The function keeps summing the element at index n and calls itself with n-1. Base Case: If n == 0, return the first element. Recursive Case: Return arr[n] + sum(n – 1). Approach: If n == 0, return arr[0]. Otherwise, return arr[n] + sum(n – 1). Time & Space Complexity:…

🌙 Problem Statement: Write a function sum(n) that calculates the sum of the first n natural numbers using recursion. Example: Input: 5 Process: 5 + 4 + 3 + 2 + 1 = 15 Output: 15 Concepts: Recursion: A technique where a function calls itself with a reduced subproblem. Base Case: Stops recursion to prevent infinite calls. Here, if n === 0, return 0. Recursive Case: Return n + sum(n – 1). Approach: Use recursion to reduce the problem. Base case: if n === 0, return 0. Recursive case:return n + sum(n-1). This keeps adding numbers until n reaches 0,…

🌙 Recursion Recursion is a technique where a function calls itself to solve a problem by breaking it down into smaller sub-problems. Base Condition: Every function call in recursion is stored in the call stack. If the recursion is too deep or has no base condition, the call stack keeps growing until memory is exhausted, causing a stack overflow error. A base condition is essential in recursion. It stops the recursion when a certain condition is met. Without it, recursion goes infinite and causes a stack overflow. if (num === 0) return;. Approach: Problem: Print numbers from n to 1…

🌙 Backtracking Recursive Algorithmic technique for solving problems incrementally by trying partial solutions and then abandoning them (backtracking) is they fail to satisfy constraints. Note: Exploring all possibility but being smart by abandoning wrong path early. Example: Like trying all the paths in max and going back if you hit a wall. When to use Backtracking ? You want to explore all combination/permutations/subsets. When there is a Clear way to validate a partial solution. Number of combinations is too large to brute force, so you abandon the invalid ones early. Basically, Backtracking optimise Recursion. Note: Try a choice -> work…

🌙 Problem Statement Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order. Example 1: Input: nums = [1,1,2] Output: [[1,1,2], [1,2,1], [2,1,1]] Example 2: Input: nums = [1,2,3] Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] Constraints 1 0 && nums[i] == nums[i-1] && !used[i-1]) continue; used[i] = true; path.add(nums[i]); backtrack(nums, used, path, result); path.remove(path.size() – 1); used[i] = false; } } } class Solution { public: vector permuteUnique(vector& nums) { vector result; sort(nums.begin(), nums.end()); vector path; vector used(nums.size(), false); backtrack(nums, used, path, result); return result; } void backtrack(vector& nums, vector& used, vector& path, vector& result) {…

🌙 Problem Statement Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s. Example 1: Input: s = “aab” Output: [[“a”,”a”,”b”],[“aa”,”b”]] Example 2: Input: s = “a” Output: [[“a”]] Constraints 1 { if(!remainingString.length) { result.push([…path]); } for(let i=1; i