CODEWITHSUNDEEP
arrayscfor-loop
User1990
User1990

Reputation: 171

Found 2 liner C solution with ',' operator in for loop, can someone explain given comma operator statement?

Explanation:

I've following problem statement at hand, I came across an interesting 2 liner, C solution for it under leedcode discussion section. I tried to decompose it to understand what it means, and except one small line, I understood the rest. My question is at the end.

Leetcode Problem Statement:

Given an array arr of positive integers sorted in a strictly increasing order, and an integer k. Find the kth positive integer that is missing from this array.

Example 1: Input: arr = [2,3,4,7,11], k = 5 Output: 9

Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5th missing >>positive integer is 9.

Example 2: Input: arr = [1,2,3,4], k = 2 Output: 6

Explanation: The missing positive integers are [5,6,7,...]. The 2nd missing positive integer is 6.

Constraints:

  1. 1 <= arr.length <= 1000
  2. 1 <= arr[i] <= 1000
  3. 1 <= k <= 1000
  4. arr[i] < arr[j] for 1 <= i < j <= arr.length

Two liner C solution:

    int findKthPositive(int* arr, int arrSize, int k){
        for (int arrCurrIndex = 0, counter = 1 ; (k && (arrCurrIndex < arrSize) ? ((arr[arrCurrIndex] != counter) ? k-- : ++arrCurrIndex) : k--) || (k = counter-1, 0) ; counter++);
        return k;
    }

For reference: Following is a similar algorithm that's being deployed, but its just cleaner to understand.


    int findKthPositive(int* arr, int arrSize, int k){ 
        for (int counter=1, arrCurrIndex=0; counter<10000; counter++) { 
            // exceed arr limits 
            if (arrCurrIndex < arrSize) { 
                if (counter == arr[arrCurrIndex]) { // found element in array 
                    index++; 
                    continue; 
                } 
            } 
            // missing element 
            k--; 
            if (k==0) { 
                return counter; 
            } 
        } 
        return 0; 
    }

My question:

What does following line in solution #1 means exactly?

(k = counter-1, 0)

======UPDATE ON ANSWER=======

I modified solution #1 in question slightly to make it more readable. It highlights what is going on with the given statement in question. Here is the modified solution:

int findKthPositive(int* arr, int arrSize, int k){
    // move counter out of the foor loop
    int counter=1;
    for (int arrCurrIndex = 0; 
    (k && (arrCurrIndex < arrSize) ? 
    ((arr[arrCurrIndex] != counter) ? k-- : ++arrCurrIndex) 
    : k--); counter++);
    return counter-1;    
}

Upvotes: 2

Views: 111

Answers (1)

Roberto Caboni
Roberto Caboni

Reputation: 7490

The binary comma operator , evaluates the first operand, discards the result and then evaluates the second one.

In the expression you posted we have

... || (k = counter-1, 0) ;

so counter-1 is actually assigned to k but its evaluation (k itself) is discarded so that 0 is used. Why 0? Because it is the neutral operand for logic or operator ||. In fact

X || 0 ==> X

In other words we have the expression

stuff_at_the_left || (k = counter-1, 0 )

that is evaluated as

stuff_at_the_left || 0

And since 0 is the neutral operand in logical or, the final evaluation is stuff_at_the_left.

The purpose of this weird expression is to cheat: the author at some point needed to assign that value to k but without adding more lines "ruining" the one liner. So they included the assignment in the logical expression making it neutral with comma operator combined with or operator's neutral operand.
We also have to say that the assignment k=counter-1, 0 is performed only if all stuff_at_the_left is evaluated as 0 (due to the short circuiting nature of logical operators in C). The resulting expanded code is

if (!stuff_at_the_left)
    k= counter-1;

Note: the comma operator has the lowest precedence among all the operators in C, and that's why the assignment is performed at first.

Upvotes: 2

Related Questions