Author: akshay

What is a Fibonacci Number? The Fibonacci sequence is a famous mathematical series in which each number is the sum of the 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,…

Write a recursive function isPowerOfTwo(n) that returns true if n is a power of 2, otherwise 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) (due to recursion stack) Examples Input: 8 Output: true (8 → 4 → 2 → 1) Input: 18 Output: false JavaScript C C++…

Write a recursive function fact(n) that returns the factorial of a number n. Concepts Recursion: Repeatedly multiply n with fact(n – 1). Base Case: fact(1) = 1 Recursive Case: n * fact(n – 1) Time & Space Complexity Time Complexity: O(n) Space Complexity: O(n) (recursive stack) Examples Input: 5 Output: 120 (5 * 4 * 3 * 2 * 1) Approach If n == 1, return 1 (base case). Else, return n * fact(n – 1). JavaScript C C++ Java Python C# function fact(n) { if (n === 1) return 1; return n * fact(n – 1); } console.log(fact(5)); //…

Write a recursive function sum(n) that calculates the sum of all odd numbers in an array arr up to index n. Concepts Recursion: Repeatedly check whether arr[n] is odd, and add it only if 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). Time & Space Complexity Time Complexity: O(n) Space Complexity: O(n) (recursive call stack) Examples Input: [5, 2, 6, 1, 3] Odd numbers: 5, 1, 3 Output: 9 Approach Check if arr[n] is odd. If yes, add it to recursive result of sum(n-1).…

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. 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). Time & Space Complexity Time Complexity: O(n) – one recursive call per element. Space Complexity: O(n) – due to call stack. Examples Input: [5, 2, 6, 1, 3] Output: 17 // 5 + 2 + 6 + 1 + 3 = 17…

Write a function sum(n) that calculates the sum of the first n natural numbers using recursion. 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). Time & Space Complexity Time Complexity: O(n) – one call per value from n to 0. Space Complexity: O(n) – due to call stack in recursion. Examples Input: 5 Output: 15 // 5 + 4 + 3 + 2 + 1 = 15 Approach If n === 0,…

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 using recursion.…

Pattern 1 – Print n x n Star Square Print a square pattern of stars (*) of size n x n. Example Output **** **** **** **** Approach Outer Loop (Rows): Run from i = 0 to i = n – 1. Inner Loop (Columns): For each row, loop from j = 0 to j = n – 1. Build Row String: Append * in each inner loop iteration. Print Row: After the inner loop, print the complete row string. Time & Space Complexity Time Complexity: O(n^2) Space Complexity: O(n) (temporary row string) JavaScript Java C++ C Python let n…

Write a function countDigits(n) that takes an integer n and returns how many digits it contains. Requirements Handles both positive and negative integers. Return 1 if n is 0 (since 0 is a single-digit number). Constraints Time Complexity: O(log₁₀(n)) — Each division reduces one digit. Space Complexity: O(1) — Only a few variables are used. Examples Input: 259 Output: 3 Input: -1035 Output: 4 Input: 0 Output: 1 Step-by-Step Approach Handle Zero: If n == 0, return 1 directly. Convert to Positive: Use abs(n) to ignore sign. Initialize a counter: Set count = 0. Loop: While n > 0: Divide…

Write a function isPalindrome(x) that takes an integer x and returns true if it reads the same backward and forward; otherwise false. Requirements Handles both positive and negative integers. Returns false for negative numbers (not palindromes). Constraints Time Complexity: O(d) where d is the number of digits. Space Complexity: O(1) — Only a few variables are used. Examples Input: 121 Output: true Input: -121 Output: false Input: 10 Output: false Step-by-Step Approach Handle Negatives: If x < 0, return false. Store Original: Save the input in xCopy for comparison. Reverse: Initialize rev = 0. While x > 0: rem =…