Algorithms for Coding Interviews in C++/

...

/

Solution: Nested Loop with Multiplication (Intermediate)

Solution: Nested Loop with Multiplication (Intermediate)

Here's a solution review for the exercise in the last lesson.

We'll cover the following...

Solution #

Press + to interact
int main(){
  int n = 10;   
  int sum = 0;  
  int j = 1;  
  float pie = 3.14;   
  
  for (int i = 1; i < n; i+=3){  // O(n/3)
    cout << pie << endl;    // 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)
  }
  cout << sum << endl; 
}

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

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