Data Structures for Coding Interviews in C#/

...

/

Solution Review: Nested Loop with Multiplication (Basic)

Solution Review: Nested Loop with Multiplication (Basic)

This review provides a detailed analysis of how to solve the “Nested Loop with Multiplication” problem.

We'll cover the following...

Solution #

The code for this challenge is reproduced below:

Press + to interact
namespace Chapter_1
{
    class Challenge_4
    {
        static void Main(string[] args)
        {
            int n = 10;    
            int sum = 0;
            int counter = 1;
            float pie = 3.14f;
            while (counter < n) // O(log3 n)
            {
                Console.WriteLine(pie); // O(log3 n)
                for (int j = 1; j < n; j += 2)// O((log3 n)*(n/2)) 
                {
                    sum += 1;// O((log3 n)*(n/2))
                }
                counter *= 3;// O(log3 n)
            }
            Console.WriteLine(sum);
            return;
        }
    }
}

Time complexity

The outer loop in this problem runs log3(n)log_3(n) times since counter will first be equal to 11, then 33, then 6, then 99 ...