Data Structures for Coding Interviews in C++/

...

/

Solution: Nested Loop with Multiplication (Pro)

Solution: 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 #

Press + to interact
C++
int main(){
  int n =10;    // O(1)
  int sum = 0;  // O(1)
  int j = 1;    // O(1)
  float pie = 3.14; // O(1)
  
  for (int i = 0; i < n; i++){ // O(n)
    cout << pie << endl; // O(n)
    while (j < i){ // O(log2(n))
      sum+=1; // O(log2(n))
      j*=2;  // O(log2(n))
    }
  }
  cout << sum << endl; // 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, immediately, j is doubled. Note that j is not reset to 1 in the code since the j is immediately doubled, therefore 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++
...
Ask