Multiple conditions in while loop giving different result

Question

I have two conditions in the while loop as:

count = 0;
while (j >= 0 && arr[j] > key)
       {
           count++;
           j = j-1;
       }

When I break these two conditions as following, the count gets changed:

while (j >= 0)
{
    if(arr[j] > key)
    {
        count++;
    }
    j = j-1;
}

Output from first program: 456

Output from second program: 904.

I thought these two blocks of code are identical. Why is the count getting different on these two programs?

Answer 1

For first case your statements

count++;

j = j-1

will be executed while both the conditions j >= 0 and arr[j] > key are true.

But for second case the statement j = j-1 will be executed only while j>=0 is true and the statement count++ will be executed while both the conditions j >= 0 and arr[j] > key are true. :)

Answer 2

Let's check both loops: Let j = 10, let key = 3 and arr[] = {1,2,3,4,5,6,7...}

In the first loop we have this pattern:

count = 0;
while ( j >= 0 && arr[j] > key ) {
    count++; 
    j = j-1;
}

Output each step:

while ( /*j = */ 10 >= 0 && /*arr[10] = */ 11 > 3 ) { // TRUE
    count++; // count becomes 1
    j = j-1; // j becomes 9
}

while ( 9 >= 0 && 10 > 3 ) { // TRUE
    count++; // count becomes 2
    j = j-1; // j becomes 8
}

while ( 8 >= 0 && 9 > 3 ) {  // TRUE
    count++; // count becomes 3
    j = j-1; // j becomes 7
}

while ( 7 >= 0 && 8 > 3 ) { // TRUE
    count++; // count becomes 4
    j = j-1; // j becomes 6
}

while ( 6 >= 0 && 7  > 3 ) { // TRUE
    count++; // count becomes 5
    j = j-1; // j becomes 5
}

while ( 5 >= 0 && 6 > 3 ) { // TRUE
    count++; // count becomes 6
    j = j-1; // j becomes 4
}

while ( 4 >= 0 && 5 > 3 ) { // TRUE
    count++; // count becomes 7
    j = j-1; // j becomes 3
}

while ( 3 >= 0 && 4 > 3 ) { // TRUE
    count++; // count becomes 8
    j = j-1; // j becomes 2
}

while ( 2 >= 0 && 3 > 3 ) { // FALSE 
    // loop breaks: First Condition TRUE, Second Condition FALSE
}

Simplified Output:

// Initial count = 0, j = 10, constant key = 3, arr[] = {1,2,3,4,5,6,7...}

count = 0  j = 10  arr[10] = 11 compound condition = true
count = 1  j = 9   arr[9]  = 10 compound condition = true
count = 2  j = 8   arr[8]  = 9  compound condition = true
count = 3  j = 7   arr[7]  = 8  compound condition = true
count = 4  j = 6   arr[6]  = 7  compound condition = true
count = 5  j = 5   arr[5]  = 6  compound condition = true
count = 6  j = 4   arr[4]  = 5  compound condition = true
count = 7  j = 3   arr[3]  = 4  compound condition = true
count = 8  j = 2   arr[2]  = 3  compound condition = false

count = 8 // 8 times it looped successfully

---

In the 2nd loop we have this pattern:

while (j >= 0) {
    if(arr[j] > key) {
        count++;
    }
    j = j-1;
}

Using the same initial conditions from the first loop above where j = 10, key = 3 and arr[] = {1,2,3,4,5,6,7...}...

Let's output each step:

while ( /*j = */ 10 >= 0 ) { // TRUE
    if( /*arr[10] = */ 11  > 3 ) {  // TRUE
        count++; // count becomes 1
    }
    j = j-1; // j becomes 9
}

while ( 9 >= 0 ) { // TRUE
    if ( 10 > 3 ) { // TRUE
        count++; // count becomes 2
    }
    j = j-1; // j becomes 8
}

while ( 8 >= 0 ) { // TRUE
    if ( 9 > 3 ) { // TRUE
        count++; // count becomes 3
    }
    j = j-1; // j becomes 7
}

while ( 7 >= 0 ) { // TRUE
    if ( 8 > 3 ) { // TRUE
        count++; // count becomes 4
    }
    j = j-1; // j becomes 6
}

while ( 6 >= 0 ) { // TRUE
    if ( 7 > 3 ) { // TRUE
        count++; // count becomes 5
    }
    j = j-1; // j becomes 5
}

while ( 5 >= 0 ) { // TRUE
    if ( 6 > 3 ) { // TRUE
        count++; // count becomes 6
    }
    j = j-1; // j becomes 4
}

while ( 4 >= 0 ) { // TRUE
    if ( 5 > 3 ) { // TRUE
        count++; // count becomes 7
    }
    j = j-1; // j becomes 3
}

while ( 3 >= 0 ) { // TRUE
    if ( 4 > 3 ) { // TRUE
        count++; // count becomes 8
    }
    j = j-1; // j becomes 2
}

while ( 2 >= 0 ) { // TRUE
    if ( 3 > 3 ) { // FALSE
        count++; // count DOES NOT INCREMENT
    }
    j = j-1; // j becomes 1
}

while ( 1 >= 0 ) { // TRUE
    if ( 2 > 3 ) { // FALSE
         count++; // count DOES NOT INCREMENT
    }
    j = j-1; // j becomes 0
}

while ( 0 >= 0 ) { // TRUE
    if ( 1 > 3 ) { // FALSE
        count++; // count DOES NOT INCREMENT
    }
    j = j-1; // j becomes -1
}

while( -1 >= 0 ) { // FALSE
    // Loop breaks since its only condition if false.
}

Simplified Output:

// Initial count = 0, j = 10, constant key = 3, arr[] = {1,2,3,4,5,6,7...}

count = 0  j = 10  arr[10] = 11 while condition = true  | if condition = true
count = 1  j = 9   arr[9]  = 10 while condition = true  | if condition = true
count = 2  j = 8   arr[8]  = 9  while condition = true  | if condition = true
count = 3  j = 7   arr[7]  = 8  while condition = true  | if condition = true
count = 4  j = 6   arr[6]  = 7  while condition = true  | if condition = true
count = 5  j = 5   arr[5]  = 6  while condition = true  | if condition = true
count = 6  j = 4   arr[4]  = 5  while condition = true  | if condition = true
count = 7  j = 3   arr[3]  = 4  while condition = true  | if condition = true
count = 8  j = 2   arr[2]  = 3  while condition = true  | if condition = false
count = 8  j = 1   arr[1]  = 2  while condition = true  | if condition = false
count = 8  j = 0   arr[0]  = 1  while condition = true  | if condition = false
count = 8  j = -1  NO EXECUTION  while condition = false | NO EXECUTION

count = 8; // 11 times it looped successfully.

These two loops are not the same and do not have the same behavior. The second while loop is going to execute more times than the first while loop.

Answer 3

In the first loop j decreases only when arr[j] > key condition is true. In the second loop j decreases every step. Let's say that arr[0] < key then the first loop will make 0 iterations, this example is the best illustration of these loops difference.

Answer 4

The two versions are not logically equivalent. In the first version, j gets decremented only when both conditions are true. In the second version j gets decremented only when the first condition is true. j still gets decremented when the key comparison fails in the second version.

Because j is used as part of computing the loop's condition, this directly affects how many times the loop gets executed.