Data Structures for Coding Interviews in C#/

...

/

Solution Review: Nested Loop with Multiplication (Intermediate)

Solution Review: Nested Loop with Multiplication (Intermediate)

This review provides a detailed analysis of how to solve the "Nested Loop with Multiplication (Intermediate)" problem.

We'll cover the following...

Solution #

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

  • The outer loop index i goes: 1,3,6,9,⋯ ,n1,3,6,9,\cdots,n. That means that the outer loop has n3\frac{n}{3} iterations.

  • The inner loop index j goes: 1,3,9,27,⋯ ,n1,3,9,27,\cdots,n. That means that an inner loop has log3(n)log_3(n) iterations. ...

Statement Number of Executions
int n = 10;
1
int sum = 0;
1
int j = 1;
1
float pie = 3.14;
1
int i=1;
11
i<n;
n3+1\frac{n}{3}+1
i+=3
n3\frac{n}{3}
Console.WriteLine(pie);