Forem: Purav Patel

Understanding Fast Power (Exponentiation by Squaring) - Pow(x, n) Step-by-Step - LeetCode 50

Purav Patel — Fri, 20 Feb 2026 18:42:39 +0000

With Clear Diagrams + Recursive & Iterative Methods (C#)

When solving Pow(x, n) in interviews (Google, Meta, etc.), a
brute-force solution is NOT enough.

The naive way:

x * x * x * x * ... (n times)

This takes O(n) time.

But we can do better.

We can solve it in:

O(log n)

Let's understand this deeply --- visually and line-by-line.

🧠 The Key Mathematical Insight

If n is EVEN:

x^n = (x^(n/2))²

Example:

2^8
= (2^4)²
= (16)²
= 256

Why?

Because:

2^8 = 2×2×2×2×2×2×2×2
     = (2×2×2×2) × (2×2×2×2)
     = 2^4 × 2^4

If n is ODD:

x^n = (x^((n-1)/2))² × x

Example:

2^9
= 2 × 2^8
= 2 × (2^4)²

We remove one x to make the exponent even.

🚀 Why This Is Faster

Instead of reducing:

n → n-1 → n-2 → ...

We reduce:

n → n/2 → n/4 → n/8 → ...

So recursion depth becomes:

O(log n)

📘 Recursive Method (C#)

public class Solution {
    public double MyPow(double x, int n) {
        long N = n;

        if (N < 0) {
            x = 1 / x;
            N = -N;
        }

        return FastPow(x, N);
    }

    private double FastPow(double x, long n) {
        if (n == 0) return 1;

        double half = FastPow(x, n / 2);

        if (n % 2 == 0)
            return half * half;
        else
            return half * half * x;
    }
}

🔍 Recursive Flow Diagram (Example: 2^13)

FastPow(2,13)
    ↓
FastPow(2,6)
    ↓
FastPow(2,3)
    ↓
FastPow(2,1)
    ↓
FastPow(2,0)

Now it builds back up:

2^0 = 1
2^1 = 1×1×2 = 2
2^3 = 2×2×2 = 8
2^6 = 8×8 = 64
2^13 = 64×64×2 = 8192

✔ Final Answer: 8192

🧠 What Happens in Memory (Call Stack)

At deepest recursion:

FastPow(2,13)
  FastPow(2,6)
    FastPow(2,3)
      FastPow(2,1)
        FastPow(2,0)

Then it unwinds upward.

Maximum stack depth:

log₂(13) ≈ 4 levels

⚡ Iterative Method (More Interview Friendly)

This avoids recursion entirely.

public double MyPow(double x, int n) {
    long N = n;

    if (N < 0) {
        x = 1 / x;
        N = -N;
    }

    double result = 1;

    while (N > 0) {
        if ((N & 1) == 1) {
            result *= x;
        }

        x *= x;
        N >>= 1;
    }

    return result;
}

🔍 Iterative Flow (2^13)

Binary of 13:

13 = 1101₂

We process bits from right to left:

Step	N	Action	x becomes
1	13 (odd)	result *= x	x²
2	6	skip	x⁴
3	3 (odd)	result *= x	x⁸
4	1 (odd)	result *= x	x¹⁶

Final result = 8192

⏱ Complexity

Method	Time Complexity	Space Complexity
Recursive	O(log n)	O(log n)
Iterative	O(log n)	O(1)

🎯 Final Takeaways

Never multiply x n times.
Use divide-and-conquer.
Always convert n to long to avoid overflow.
Prefer iterative version in interviews.

If this helped you understand recursion better, try implementing it
yourself without looking at the solution!

Understanding the K-th Character in the String Game (Step-by-Step) - LeetCode 3304

Purav Patel — Wed, 18 Feb 2026 00:25:21 +0000

Problem Summary

Alice and Bob are playing a game. Initially, Alice has a string word = "a".

You are given a positive integer k.

Now Bob will ask Alice to perform the following operation forever:

Generate a new string by changing each character in word to its next character in the English alphabet, and append it to the original word.
For example, performing the operation on "c" generates "cd" and performing the operation on "zb" generates "zbac".

Return the value of the kth character in word, after enough operations have been done for word to have at least k characters.

Example 1:

Input: k = 5

Output: "b"

Explanation:

Initially, word = "a". We need to do the operation three times:

Generated string is "b", word becomes "ab".
Generated string is "bc", word becomes "abbc".
Generated string is "bccd", word becomes "abbcbccd".

Example 2:

Input: k = 10

Output: "c"

Constraints:

1 <= k <= 500

We start with:

word = "a"

Each operation transforms the string like this:

new_word = old_word + shifted(old_word)

Where shifted(old_word) means each character moves to the next
alphabet letter:

'a' → 'b'
'b' → 'c'
...
'z' → 'a' (wrap around)

The string length doubles every step:

1 → 2 → 4 → 8 → 16 → ...

We must return the k-th character without building the full string.

🧠 Key Insight

At every stage:

S(n) = S(n-1) + shifted(S(n-1))

Which means:

First half → previous string
Second half → shifted(previous string)

So any index k must either:

Be in the first half → same index in previous stage
Be in the second half → map to (k - half) in previous stage, then shift +1

✅ Recursive Implementation

public class Solution {
    public char KthCharacter(int k) {
        return Solve(k);
    }

    private char Solve(int k) {
        if (k == 1) return 'a';

        int length = 1;
        while (length < k) {
            length *= 2;
        }

        int half = length / 2;

        char prev = Solve(k - half);
        return (char)('a' + (prev - 'a' + 1) % 26);
    }
}

🔍 Step-by-Step Example (k = 6)

Step 1

Smallest power of 2 ≥ 6 → 8
Half = 4

6 > 4 → second half
Call Solve(6 - 4) → Solve(2)

Step 2

Smallest power of 2 ≥ 2 → 2
Half = 1

2 > 1 → second half
Call Solve(2 - 1) → Solve(1)

Step 3

Solve(1) → return 'a'

Unwinding

Solve(2): 'a' → shift → 'b'

Solve(6): 'b' → shift → 'c'

✅ Final Answer: 'c'

🧠 What's Happening in Memory

Call stack during execution:

Solve(6)
  → Solve(2)
      → Solve(1)

As recursion unwinds:

Solve(1) returns 'a'
Solve(2) returns 'b'
Solve(6) returns 'c'

Each time we were in the second half, we applied one shift.

⏱ Time & Space Complexity

Time: O(log k)
Space: O(log k) (due to recursion stack)

🔥 Final Takeaway

We never build the full string.

Instead, we:

Keep reducing k
Track how many times we land in the second half
Shift the base character 'a' accordingly

This is classic divide-and-conquer recursion.

If this helped you understand recursion better, try implementing the
iterative version next for even better performance.

Building a Modern Full-Stack Application: Architecture First

Purav Patel — Tue, 17 Feb 2026 05:40:14 +0000

The Journey Begins

Ever started a project that seemed simple at first, only to watch it spiral into a tangled mess of spaghetti code? I've been there. But what if I told you that spending time upfront on architecture could save you hundreds of hours of refactoring later?

In this series, I'm going to walk you through building a production-ready full-stack application with clean architecture principles. This isn't theoretical fluff—this is real code, real patterns, and real lessons learned from building an enterprise-level tutoring management system.

What we'll build:

A modern .NET 9 Web API backend
A React 19 + TypeScript frontend
PostgreSQL database with Entity Framework Core
Azure AD authentication
Real-time features and background processing

But more importantly, we'll build it the right way—with clean architecture, proper layering, and maintainable patterns that scale.

In this first post, we'll understand WHY architecture matters by looking at what happens when you skip it. We'll see the real problems that emerge and why "we'll fix it later" never works.

The Cost of "We'll Fix It Later"

Here's what typically happens when you skip architecture:

Week 1: "Let's just get something working"

Direct database calls in controllers
No thought to testing
"We'll clean it up later"

Month 3: "We need to add features fast"

Copy-paste existing code
Each developer does things differently
Technical debt accumulating

Month 6: "Why is everything breaking?"

Changes in one place break unrelated features
Can't add tests (too tightly coupled)
Fear of touching existing code

Month 12: "We need to rewrite this"

Too expensive to fix
Business pressure to keep adding features
Team morale drops

The Truth: Later never comes. Technical debt compounds like credit card interest. What takes 1 hour to do right initially will take 10 hours to fix later, or 100 hours to rewrite.

Architecture First vs. Code First

Code First Approach:

Start coding → Hit problems → Try to refactor → Too late → Live with mess

✅ Fast initial progress
❌ Slows down dramatically over time
❌ Hard to test
❌ Difficult to maintain
❌ Expensive to change

Architecture First Approach:

Plan architecture → Implement with patterns → Maintain structure → Scale easily

⚠️ Slower initial start (1-2 days planning)
✅ Consistent velocity over time
✅ Easy to test
✅ Simple to maintain
✅ Changes are isolated and safe

Real-world analogy: Building a house. You can start nailing boards together and see progress immediately, but without a blueprint, you'll end up with crooked walls and no plumbing. Architects spend weeks on blueprints because it saves months during construction.

A Real Example: What Happens Without Architecture

Let me show you exactly what happens when you skip architecture. Here's real code that "works" but creates problems:

// Controller.cs - This is what happens without architecture
public class StudentController : ControllerBase
{
    [HttpGet]
    public async Task<IActionResult> GetStudents()
    {
        // Direct database access in controller? Bad!
        using var connection = new NpgsqlConnection("connection_string");
        var students = await connection.QueryAsync<Student>("SELECT * FROM Students");

        // Business logic in controller? Also bad!
        foreach(var student in students)
        {
            if(student.Age < 18)
                student.RequiresParentalConsent = true;
        }

        // Returning database entities directly? Triple bad!
        return Ok(students);
    }
}

Let's Understand Why This Is Problematic

Let me walk you through what's happening here and why each line is a problem:

Line 1: Direct Database Connection

using var connection = new NpgsqlConnection("connection_string");

What this does: Creates a direct connection to PostgreSQL database from the controller.

Why it's bad:

Your controller now KNOWS about PostgreSQL specifically. Want to switch to SQL Server tomorrow? You'll have to change your controller code.
The connection string is hardcoded (or at best, injected here), meaning the controller is responsible for database connectivity.
Testing becomes impossible - to test this method, you need an actual database running. No unit tests possible!

Real-world analogy: It's like a restaurant waiter walking into the kitchen, cooking the food themselves, and serving it. The waiter should just take orders and deliver food - not know how to operate the stove!

Line 2: Direct Database Query

var students = await connection.QueryAsync<Student>("SELECT * FROM Students");

What this does: Executes a raw SQL query and maps results to Student objects.

Let's break down the complex terms:

"Raw SQL query" - This is a direct database command written in SQL (Structured Query Language), the language databases understand. It's "raw" because you're writing the actual database commands yourself instead of using a higher-level abstraction.

"Maps results to Student objects" - The database returns rows of data (like Excel spreadsheet rows). The QueryAsync<Student> method takes those rows and converts them into C# Student objects:

Database returns:
┌────┬───────────┬─────┬──────────┐
│ Id │ Name      │ Age │ Email    │
├────┼───────────┼─────┼──────────┤
│ 1  │ John Doe  │ 20  │ j@s.com  │
│ 2  │ Jane Doe  │ 19  │ ja@s.com │
└────┴───────────┴─────┴──────────┘

Gets "mapped" to C# objects:
new Student { Id = 1, Name = "John Doe", Age = 20, Email = "j@s.com" }
new Student { Id = 2, Name = "Jane Doe", Age = 19, Email = "ja@s.com" }

Why it's bad:

Your controller now knows about database tables and SQL syntax
If the Students table structure changes, you must change the controller
You're selecting ALL columns (SELECT *) even if you only need a few
SQL injection risks if you ever add parameters ← This is CRITICAL!

Understanding SQL Injection - A Security Nightmare

What is SQL Injection?

SQL injection is when an attacker tricks your application into running malicious database commands. It's one of the most dangerous security vulnerabilities.

Vulnerable Code Example:

// NEVER DO THIS! ☠️ Extremely dangerous!
public async Task<IActionResult> GetStudentByName(string name)
{
    // Building query by concatenating user input
    var query = "SELECT * FROM Students WHERE Name = '" + name + "'";
    var student = await connection.QueryAsync<Student>(query);
    return Ok(student);
}

What happens when a normal user searches for "John"?

-- Query becomes:
SELECT * FROM Students WHERE Name = 'John'
-- ✅ Works fine, returns John's record

What happens when an ATTACKER enters: John'; DROP TABLE Students; --

-- Query becomes:
SELECT * FROM Students WHERE Name = 'John'; DROP TABLE Students; --'
-- ☠️ DISASTER! This:
-- 1. Selects John
-- 2. DELETES YOUR ENTIRE STUDENTS TABLE
-- 3. -- comments out the rest

Your entire Students table is GONE! All student data. Deleted. Forever.

Even worse attacks:

-- Attacker enters: ' OR '1'='1
SELECT * FROM Students WHERE Name = '' OR '1'='1'
-- ☠️ Returns ALL students (security breach - data exposure)

-- Attacker enters: '; UPDATE Students SET GPA = 4.0 WHERE Name = 'Attacker'; --
SELECT * FROM Students WHERE Name = ''; UPDATE Students SET GPA = 4.0 WHERE Name = 'Attacker'; --'
-- ☠️ Changes grades in database (data manipulation)

-- Attacker enters: '; SELECT password, email FROM Users; --
-- ☠️ Steals passwords (credential theft)

Why this happens:

User input is treated as code instead of data
The database can't tell the difference between your intended query and the attacker's injected commands
It's like giving someone a form to fill out and they write instructions in the blank spaces that you then follow blindly

The Safe Way - Parameterized Queries:

// ✅ Safe - Using parameters
public async Task<IActionResult> GetStudentByName(string name)
{
    var query = "SELECT * FROM Students WHERE Name = @Name";
    var student = await connection.QueryAsync<Student>(query, new { Name = name });
    return Ok(student);
}

What changes?

@Name is a parameter placeholder
The value is passed separately: new { Name = name }
The database driver automatically escapes the input
User input is treated as data, never as code

When attacker enters: John'; DROP TABLE Students; --

-- Query stays:
SELECT * FROM Students WHERE Name = @Name
-- But the parameter value is:
@Name = "John'; DROP TABLE Students; --"
-- Database treats the ENTIRE string as the name to search for
-- It looks for a student literally named "John'; DROP TABLE Students; --"
-- Finds nothing, returns empty result
-- ✅ Your table is SAFE!

Real-world impact:

2008: Heartland Payment Systems - 134 million credit cards stolen via SQL injection
2012: Yahoo - 450,000 passwords leaked
2017: Equifax breach - 147 million people affected (initially exploited a different vulnerability, but SQL injection was found in their systems)
SQL injection has been in the OWASP Top 10 security risks for over a decade

The lesson: NEVER concatenate user input into SQL queries. Always use parameterized queries or ORMs (like Entity Framework) that handle this automatically.

Line 3-6: Business Logic in Controller

foreach(var student in students)
{
    if(student.Age < 18)
        student.RequiresParentalConsent = true;
}

What this does: Loops through students and applies a business rule.

Why it's bad:

This business rule ("under 18 requires parental consent") should be reusable
What if you need this logic in 10 different places? Copy-paste it 10 times?
Controllers should coordinate, not calculate
This logic can't be unit tested separately

Line 7: Returning Database Entities

return Ok(students);

What this does: Sends the Student database entity directly to the API caller.

Why it's REALLY bad:

You're exposing your internal database structure to the world
If Student entity has sensitive fields (SSN, password hash), they're now public
Changing your database means breaking your API contract
Circular references in entities can crash JSON serialization

The Ripple Effects: A Timeline of Pain

This code works today, sure. But watch what happens over time:

Month 1: "Let's add filtering by grade level"

Now you have SQL queries scattered across multiple controllers
Each controller has slightly different filtering logic
Bugs multiply because logic is duplicated

Month 3: "We need to switch from PostgreSQL to SQL Server"

You must modify EVERY SINGLE CONTROLLER
50+ files changed, hundreds of lines modified
High risk of bugs
Weekend deployment becomes a week-long migration

Month 6: "Let's add unit tests"

Every test requires a real database
Tests are slow (100-1000ms each instead of <1ms)
Tests fail if database is down or has wrong data
Basically untestable without complex infrastructure

Month 12: "The API is exposing sensitive data!"

Emergency security patch needed
Must audit every single endpoint
Can't tell what data is being exposed where
Compliance violations, potential lawsuits

Year 2: "We need to add caching"

Every controller must be modified
Caching logic duplicated everywhere
Some developers forget to add it
Inconsistent behavior across endpoints

Year 3: "New developer joins the team"

Takes weeks to understand where logic lives
Accidentally introduces bugs because everything is connected
Afraid to change anything
Team velocity drops to 25% of what it should be

There has to be a better way. And there is.

The Investment vs. The Return

Without Architecture:

Day 1-10: Fast progress! 🚀
Month 1-3: Slowing down... 🐌
Month 6+: Every change is risky and slow 🐢
Year 2: Considering a rewrite 💸💸💸

With Architecture:

Day 1-2: Learning and planning 📚
Day 3-10: Structured progress 🏗️
Month 1-12: Consistent velocity ⚡
Year 2+: Easy to maintain and extend ✨

The Math:

Without architecture: 100 hours saved initially, 1000+ hours of pain later
With architecture: 10 hours invested initially, 100s of hours saved over time

Architecture is not overhead. Architecture is debt prevention.

What's Next?

Now that you understand WHY architecture matters and what happens when you skip it, in Part 2 we'll explore the different architectural approaches available:

No Architecture (Script Pattern) - When is it okay?
Traditional N-Tier - Better, but still has problems
Active Record Pattern - Simple but limiting
Repository Pattern - Getting closer
Domain-Driven Design - For complex domains
Microservices - The scaling solution
Clean Architecture - The sweet spot ⭐

For each pattern, I'll show you:

Real code examples with line-by-line explanations
What problems it solves
What problems it creates
When to use it (and when NOT to)
Why Clean Architecture wins for most production applications

Key Takeaways

✅ "We'll fix it later" never happens - Technical debt compounds exponentially

✅ Without architecture, every change becomes dangerous - Fear of touching code kills velocity

✅ SQL injection is real and devastating - Billions of dollars lost due to this vulnerability

✅ Architecture is debt prevention, not overhead - 10 hours invested saves 100s later

✅ Controllers doing everything is a time bomb - Database, business logic, HTTP all mixed together

✅ Testing becomes impossible without separation - Can't test what you can't isolate

✅ Team scalability requires structure - New developers need clear boundaries

Discussion

Have you experienced the pain of "we'll fix it later"? What was the tipping point that made you invest in architecture? Share your stories in the comments below!

Next in Series: Part 2: Comparing Architectural Approaches - Finding the Right Pattern
Tags: #dotnet #csharp #architecture #softwaredevelopment #webapi #programming #technicaldebt #coding

This series is based on real experiences building an enterprise tutoring management system. All code examples have been generalized for educational purposes.