Algorithms for Coding Interviews in C++/

...

/

Solution: Nested Loop with Multiplication (Basic)

Solution: Nested Loop with Multiplication (Basic)

This review provides a detailed analysis of how to solve the nested loop with a multiplication problem.

We'll cover the following...

Solution #

The code for this challenge is reproduced below:

Press + to interact
int main(){
  int n =10;   
  int sum = 0; 
  int var = 1;  
  float pie = 3.14;
  
  while (var < n){   // O(log3 n)
    cout << pie << endl;   // O(log3 n)
    for (int j = 1; j < n; j+=2){   // O((log3 n)*(n/2)) 
      sum+=1;   // O((log3 n)*(n/2))
    }
    var*=3;    // O(log3 n)
  }
  cout << sum << endl;
}

Time Complexity

The outer loop in this problem runs log3(n)log_3(n) times since var will first be equal to 11, then 33, then 9,⋯9,\cdots ...

Access this course and 1400+ top-rated courses and projects.