Search⌘ K
Home
Courses
Data Structures for Coding Interviews in C#

Solution Review: Nested Loop with Multiplication (Pro)

This review provides a detailed analysis of the different ways to solve the "Nested Loop with Multiplication (Pro)" challenge.

We'll cover the following...

Solution #

C#
namespace Chapter_1
{
    class Challenge_7
    {
        static void Main(string[] args)
        {
            int n = 10;    // O(1)
            int sum = 0;   // O(1)
            int j = 1;     // O(1)
            float pie = 3.14f; // O(1)
            for (int i = 0; i < n; i++) // O(n)
            {
                Console.WriteLine(pie); // O(n)
                while (j < i) // O(log2(n))
                {
                    sum += 1; // O(log2(n))
                    j *= 2;   // O(log2(n))
                }
            }
            Console.WriteLine(sum); // O(1)
            
        }
    }
}

The outer loop in the main function has “n” iterations as it iterates on i from 0 to n-1. If the condition j < i is true, the inner loop is entered. However, j is doubled immediately. Note that j is not reset to 1 in the code, since the j is immediately doubled. Therefore, the inner while loop will run O(log2(n))O(log_2(n)) times for all the iterations of the outer loop.

Note: Inner while loop will run (at most) once for each iteration of the outer loop.

Statement Number of Executions
int n = 10;
1
int sum = 0;
1
int j = 1;
1
float pie = 3.14;
1
int i=0;
11
i<n;
n+1n+1
i++
...