Any base substraction

1. You are given a base b

2. You are given 2 numbers n1 and n2 of base b

3. You are required to substract n1 from n2 and print the value

Input Format:

- A base b

- A number n1

- A number n2

Output:

diff of n2 & n1 in base b

Constraints:

2 <= b <= 10

0 <= n1 <= 256

0 <= n2 <= 256

package jan19;

public class AnyBaseSubstraction {
    public static void main(String[] args) {

        int n1b8 = 1212;
        int n2b8 = 236;
        int base = 8;

        anyBaseSubstraction(n1b8, n2b8, base);
    }

    /**
     * Time Complexity: O(d), where d = number of digits in the longer number
     * Space Complexity: O(1), constant space used
     */
    private static void anyBaseSubstraction(int n1b8, int n2b8, int base) {

        int carryFromPrevious = 0, ans = 0, power = 0; // O(1)
        while (n1b8 > 0 || n2b8 > 0) { // O(d) loop where d = number of digits

            int a = n1b8 % 10;        // O(1)
            if (carryFromPrevious == -1)
                a = a - 1;            // O(1)
            int b = n2b8 % 10;        // O(1)

            n1b8 = n1b8 / 10;         // O(1)
            n2b8 = n2b8 / 10;         // O(1)

            if (a < b) {
                carryFromPrevious = -1; // O(1)
                a = a + base;           // O(1)
            }

            ans += (a - b) * (int) Math.pow(10, power++); // O(1), since power is small (integer)
        }

        System.out.println(ans); // O(1)
    }
}

📊 Complexity Table
Case
Time Complexity
Space Complexity
Explanation
Best
O(1)
O(1)
If both numbers are zero or subtraction completes in one digit.
Average
O(d)
O(1)
Where d is the number of digits in the longer of the two numbers.
Worst
O(d)
O(1)
When subtraction and borrow propagation continue for all digits.

💡 d is the number of digits, typically O(log₁₀(n)), but represented as O(d) to reflect per-digit operations in base conversions.

✅ Uses constant space as it stores only digits and a few integers, no extra data structures are used.

Any base addition

  1. You are given a base b

2. You are given 2 numbers of base b

3. You are required to add two numbers and print their values in base b.

Input Format:

- A base b

- A number n1

- A number n2

Output:

sum of n1 & n2 in base b

Constraints:

2 <= b <= 10

0 <= n1 <= 256

0 <= n2 <= 256

package jan19;

public class AnyBaseAddition {
    public static void main(String[] args) {
        int n1_b_8 = 236;
        int n2_b_8 = 754;
        int base = 8;

        sum(n1_b_8, n2_b_8, base);
    }

    /**
     * Adds two numbers given in a specific base and prints the result in that base.
     *
     * Time Complexity: O(max(d1, d2))
     * - Where d1 and d2 are the number of digits in n1 and n2.
     * - In each iteration, one digit from each number is processed.
     *
     * Space Complexity: O(1)
     * - Uses a fixed amount of space regardless of input size.
     */
    private static void sum(int n1B8, int n2B8, int base) {
        int carry = 0, ans = 0, power = 0;

        while (n1B8 > 0 || n2B8 > 0 || carry > 0) {
            int a = n1B8 % 10;
            int b = n2B8 % 10;
            n1B8 = n1B8 / 10;
            n2B8 = n2B8 / 10;

            int sum = a + b + carry;
            carry = sum / base;

            ans += (sum % base) * (int) Math.pow(10, power++);
        }

        System.out.println(ans);
    }
}

Case	Time Complexity	Space Complexity	Explanation
Best Case	O(1)	O(1)	When both numbers are 0, only one loop iteration runs.
Average Case	O(d)	O(1)	Where d is the number of digits in the longer of the two numbers.
Worst Case	O(d)	O(1)	Carries continue through all digits, requiring processing every digit.

💡 Note: The number of digits d in a number n is O(log₁₀(n)), so technically it's O(log₁₀(n)), but in competitive programming and base conversion contexts, we usually denote it as O(d) to reflect digit-based iterations.

 

First and Last Index

 Input: 

10, 20, 20, 20, 20, 20, 40, 50, 50, 60

20

Output:

1

5

package jan21;

public class FirstLastIndex {
    public static void main(String[] args) {

        int[] arr = {10, 20, 20, 20, 20, 20, 40, 50, 50, 60};
        int data = 20;

        int low = 0, high = arr.length - 1, firstIndex = -1, lastIndex = -1;

        // -----------------------
        // Find First Index
        // -----------------------

        // Time Complexity: O(log n)
        // Space Complexity: O(1)
        // Binary search to find first occurrence of 'data'
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (data > arr[mid]) {
                low = mid + 1;
            } else if (data < arr[mid]) {
                high = mid - 1;
            } else {
                firstIndex = mid;    // potential first index found
                high = mid - 1;      // move left to find earlier occurrence
            }
        }

        System.out.println(firstIndex);

        // -----------------------
        // Find Last Index
        // -----------------------

        low = 0;
        high = arr.length - 1;
        lastIndex = -1;

        // Time Complexity: O(log n)
        // Space Complexity: O(1)
        // Binary search to find last occurrence of 'data'
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (data > arr[mid]) {
                low = mid + 1;
            } else if (data < arr[mid]) {
                high = mid - 1;
            } else {
                lastIndex = mid;    // potential last index found
                low = mid + 1;      // move right to find later occurrence
            }
        }

        System.out.println(lastIndex);
    }
}

📊 Complexity Table
Case
Time Complexity
Space Complexity
Description
Best
O(log n)
O(1)
Binary search immediately finds the element on first try
Average
O(log n)
O(1)
Standard binary search behavior, divides the array in halves
Worst
O(log n)
O(1)
Element occurs multiple times (as in your example), so both full searches needed

Ceil & Floor

Find ceil and floor of number n in array.

Input:

array

number

Ceil is value in array which is just greater than n. If an element is equal to n exists that will be considered as ceil.

Floor is value in array which is just less than n. If an element is equal to n exists that will be considered as floor.

Assumption: array is sorted.

eg. 10 20 30 40 50 60 70 80 90 100

n = 55, ceil = 50; floor = 60

n = 40, ceil = 40; floor = 40

package jan21;

public class CeilFloor {
    public static void main(String[] args) {

        int[] arr = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
        int n = 33;

        int low = 0, high = arr.length - 1;
        int ceil = Integer.MAX_VALUE;
        int floor = Integer.MIN_VALUE;

        // Time Complexity: O(log n)
        // - Binary search cuts the search space in half each time.
        //
        // Space Complexity: O(1)
        // - Only a few variables used regardless of input size.

        while (low <= high) {
            int mid = low + (high - low) / 2; // O(1)
            if (arr[mid] > n) {
                high = mid - 1;
                ceil = arr[mid];      // potential ceil found
            } else if (arr[mid] < n) {
                low = mid + 1;
                floor = arr[mid];     // potential floor found
            } else {
                ceil = arr[mid];      // exact match
                floor = arr[mid];
                break;
            }
        }

        System.out.println(floor);
        System.out.println(ceil);
    }
}

📊 Time & Space Complexity Table

Case
Time Complexity
Space Complexity
Explanation
Best
O(1)
O(1)
If n is found at the first mid point
Average
O(log n)
O(1)
Binary search divides the array in half each iteration
Worst
O(log n)
O(1)
In worst case, full binary search needed without finding n exactly

Fibronacci

Input: 10

Output: 55

package jan27;

public class Fibronacci {
    public static void main(String[] args) {
        int n = 10;
        System.out.println(fibronacci(n));  // EXPECTATION
    }

    // Time Complexity: O(2^n)
    // Space Complexity: O(n) [due to recursive call stack]
    private static int fibronacci(int n) {
        if (n <= 1) return n;               // BASE CASE

        int preOrder = fibronacci(n - 1);   // FAITH
        int postOrder = fibronacci(n - 2);  // FAITH

        return preOrder + postOrder;           // WORK
    }
}

🔍 Explanation:
✅ Time Complexity: O(2^n)
The function makes two recursive calls at each step.
This creates a binary tree of calls with height n.
The total number of function calls grows exponentially, hence O(2^n).
✅ Space Complexity: O(n)
Although there are many calls, the recursive call stack depth goes up to n in the worst case.
So the space used by the stack is linear.



Case
Time Complexity
Space Complexity
Notes




Best
O(2ⁿ)
O(n)
No memoization; exponential recursive calls


Average
O(2ⁿ)
O(n)
Same as worst, as all calls happen


Worst
O(2ⁿ)
O(n)
Deepest stack with overlapping subproblems

Power Logarithmic

 

package jan27;

public class PowerLogarithmic {
    public static void main(String[] args) {
        int x = 10;
        int n = 8;
        System.out.println(powerLogarithmic(x, n));  // EXPECTATION
    }

    /**
     * Calculates x raised to the power n using divide-and-conquer.
     *
     * Time Complexity: O(log n)
     * - Each recursive call divides the exponent by 2.
     * - So total calls = log₂(n), and constant work per call.
     *
     * Space Complexity: O(log n)
     * - Due to recursive call stack. Depth of recursion is log₂(n).
     */
    private static int powerLogarithmic(int x, int n) {
        if (n == 0)
            return 1;                                               // BASE CASE

        int x_ki_power_n_by_2 = powerLogarithmic(x, n / 2);      // FAITH
        int x_ki_power_n = x_ki_power_n_by_2 * x_ki_power_n_by_2;   // WORK

        // If exponent is odd, multiply one extra x
        if (n % 2 == 1)                                             // WORK
            x_ki_power_n = x_ki_power_n * x;

        return x_ki_power_n;
    }
}

Case	Time Complexity	Space Complexity	Explanation
Best Case	O(log n)	O(log n)	The recursion depth is reduced by half each time (divide-and-conquer).
Average Case	O(log n)	O(log n)	For any n, the algorithm divides n by 2 recursively.
Worst Case	O(log n)	O(log n)	Same as average; the number of calls grows logarithmically with n.

🔍 Summary:

• ✅ Time Complexity: O(log n) — because the function divides n by 2 in each recursive call.

• ✅ Space Complexity: O(log n) — due to recursion stack frames, each level represents a halving of n.

Power (Linear)

Question

1. You are given a number x.

2. You are given another number n.

3. You are required to calculate x raised to the power n. Don't change the signature of power function

Note-> The online judge can't force you to write the function recursively but that is what the spirit of question is.

Write recursive and not iterative logic. The purpose of the question is to aid learning recursion and not test you.

Input Format

A number x

A number n

Output Format

x raised to the power n

package jan27;

public class PowerLinear {
    public static void main(String[] args) {
        int x = 2;
        int n = 4;

        System.out.println(powerLinear(x, n)); // Expected output: 16
    }

    /**
     * Calculates x raised to the power n using linear recursion.
     *
     * Time Complexity: O(n)
     * - One recursive call per decrement of n, so n total calls.
     *
     * Space Complexity: O(n)
     * - Recursion call stack grows up to depth n.
     */
    private static int powerLinear(int x, int n) {
        if (n == 0)
            return 1; // Base case corrected to n == 0 for proper exponentiation logic

        return x * powerLinear(x, n - 1);
    }
}

Case
Time Complexity
Space Complexity
Explanation
Best Case
O(n)
O(n)
All inputs require n recursive calls; no early return or shortcut possible.
Average Case
O(n)
O(n)
On average, recursion depth is still n; no input-specific optimization.
Worst Case
O(n)
O(n)
Always makes n recursive calls, maximum call stack usage.