2

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;    
}
User1990
  • 161
  • 11
  • 1
    Didn't downvote, but your title is very low on information. Furthermore, your question doesn't really have anything to do with Leetcode, but with the use of the comma operator in C and your title shoudl reflect that in some way. – dandan78 Nov 18 '20 at 20:29
  • 1
    A construct of the form `(expr1, expr2)` says evaluate `expr1`. Then, evaluate `expr2`. This can be extended: `(expr1, expr2, ..., exprN)`. The parens group them together. The final expression is the grouped result. (e.g.) `int res = (x = 3, 7);` will set `x` to `3` and `res` will be `7`. – Craig Estey Nov 18 '20 at 20:29
  • 1
    [FYI, I'm not the DVer]. For learning purposes, you can study solution #1. But, it's "cute code". It may work, but it's difficult to understand. And, serves little benefit because solution #2 will generate code that is just as efficient [with the optimizer]. So, study, but _never_ write stuff like that for production grade software. – Craig Estey Nov 18 '20 at 20:36
  • Since I agree with @dandan78 I considered editing the question but my edit would be _really_ invasive so I don't feel confortable doing it. Karan, would you simplify your question? Something like: 1) "Studying solutions to the Leetcode problem X (link) I found this code" - 2) "What is its meaning?" - 3) "just for reference, the long solution is..." – Roberto Caboni Nov 18 '20 at 20:46
  • @dandan78 Thanks, makes sense. I cleaned up the title now, and will keep it in mind in future. – User1990 Nov 18 '20 at 20:58

1 Answers1

2

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.

Roberto Caboni
  • 7,252
  • 10
  • 25
  • 39
  • Thanks @Roberto I understood the explanation. I'm trying to wrap my head around following. If this is left to right evaluation, and first value gets discarded anyway, why assign it? or does it mean, assign for first iteration (i.e. `k=counter-1`), for next iterations `k=0`? I'm trying to fathom what do you mean by `making it neutral with comma operator combined with or operator's neutral operand` ? – User1990 Nov 18 '20 at 22:00
  • @karan `k = counter-1` is discarded in composing the whole expression in logical or, but evaluated, so in the next step `k` will have the new value. – Roberto Caboni Nov 18 '20 at 22:05
  • @karan that part of the expression is `stuff_at_the_left || (k = counter-1, 0 )` that is evaluated as `stuff_at_the_left || 0 `. And since 0 is neutral in logical or ( x || 0 => 0 ) the final evaluation is `stuff_at_the_left`. – Roberto Caboni Nov 18 '20 at 22:09
  • @karan And since in logical ors a single _true_ makes the expression true as well, after the first true operand the other operands are not evaluated. This means that `k=counter-1, 0` is executed only if `stuff_at_the_left` is false. The resulting expanded code is `if (!stuff_at_the_left) k= counter-1;` – Roberto Caboni Nov 18 '20 at 22:13
  • 1
    Thanks a ton for your detailed explanation @Roberto, its much appreciated. I think I understand now when I used input as `[1,2,3,4]` and `k=2`. We will evaluate `stuff_at_the_left` until `counter = 7` then `stuff_at_the_left` becomes `0` and `stuff_at_the_right` makes `k=6 (counter -1)` and makes expression invalid with value `0` invalidating both `stuff_at_the_left` and `stuff_at_the_right` and returns `k`. I was mis-reading it as `(k=counter-1, k=0)` all this time instead of `k=counter-1; 0;`. It makes sense now. – User1990 Nov 18 '20 at 23:10