#Leetcode easy problem

49 messages · Page 1 of 1 (latest)

foggy sphinx
#

https://leetcode.com/problems/single-number/

int singleNumber(int* nums, int numsSize){
    int* intArray = (int*) calloc(600000, sizeof(int));
    for(int i = 0; i < numsSize; i++){
        intArray[nums[i]+300000]++;
    }
    for(int i = 0; i < 600000; i++){
        if(intArray[i] == 1){
            free(intArray);
            return i-300000;
        }
    }
    free(intArray);
    return 0;
}```

Learning syntax, algos and just general C stuff as I do these leetcode problems so there's likely a better way to do this.
Looking for some instructive feedback for any glaring mistakes.

I'm assuming there's a much more memory friendly solution I can't think of 8)
nocturne sentinel
#

you aren't freeing the memory if you find the number

foggy sphinx
#

o shit

foggy sphinx
nocturne sentinel
#

for changing what you have now, or different approaches?

foggy sphinx
#

Both I suppose. If my approach is a good measure worse than another approach I've failed to think of, then I'd like to see that approach if possible.

nocturne sentinel
#

Nothing major as far as what you have now. Only things I'd mention are that you don't have to cast the output of calloc/malloc, and that your last two lines are unreachable dead code

foggy sphinx
#

Casting it as my compiler was warning about it. So just to get rid of that.

nocturne sentinel
#

it really shouldn't be warning over that

foggy sphinx
#

Also noticing it now always returns -300000 with the frees in place.

#

And I hav eno idea why 😄

nocturne sentinel
#

Guessing off-by-one or something that's getting it to always trigger on the first number

foggy sphinx
#

Is i somehow getting freed too?

nocturne sentinel
#

i can't be freed

#

you can only free() memory given to you by *alloc

foggy sphinx
#

Oh

#

I'm silly. I forget without {} it'll only use the first line.

nocturne sentinel
#

As for other approaches, first thing that comes to mind is using XOR. Every number in the list has a frequency of two, except the target. Since XOR is effectively a bit toggle, you can XOR all of the numbers together. Each number that appears twice will toggle itself on, then back off with the second occurence. Only the lone number won't be toggled back off, so the final result will be the single number

nocturne sentinel
foggy sphinx
#

Saving a lot of memory I guess.

nocturne sentinel
#

you aren't XORing anything

#

you're doing the same thing, just toggling a bool array on and off instead of counting 0, 1, 2

foggy sphinx
#

I must be missing what you mean with XOring then. Leme reread.

XOR all of the numbers together. is what I'm missunderstanding I think.

#

What do you mean by that?

nocturne sentinel
#

the bitwise XOR operation

#

^

# 
a b | a ^ b
-----------
0 0 |   0
0 1 |   1
1 0 |   1
1 1 |   0
foggy sphinx
#

Ye, just looked it up and found similar looking things explaining what it is. I might be dumb but I'm lost as to where/how I could use it here.

nocturne sentinel
#

Take the input numbers [4, 1, 2, 1, 2]. If we have a variable that starts at 0, and then XOR each of those numbers into it:

# 
000 ^ 100 = 100 (4)
100 ^ 001 = 101 (5)
101 ^ 010 = 111 (7)
111 ^ 001 = 110 (6)
110 ^ 010 = 100 (4)
#

result of each is the first term of the next

#

note the ending value being the correct 4

#

when you're XORing, each 1 in first term will toggle the corresponding bit in the second

foggy sphinx
#

Oooo it's just clicked. The canceling out of the pairs so it's like they were never tested wasn't clicking in my mind.

#

I see. tyty.

nocturne sentinel
#

yeah, and then the 4 is the only number that isn't toggling itself back off

foggy sphinx
# 
int singleNumber(int* nums, int numsSize){
    int res = 0;
    for(int i = 0; i < numsSize; i++)
        res ^= nums[i];
    return res;
}```
Well. That's much much smaller, faster and memory efficient xD
And* now I have a better understanding of XOR usages.
nocturne sentinel
#

and then I also discarded the extra variable, instead using XORing the number I just read into the next, so that by the end the last index will have the result:

int singleNumber(int* nums, int numsSize){
    for(int i = 0; i < numsSize - 1; i++) {
        nums[i+1] ^= nums[i];
    }
    return nums[numsSize - 1];
}

brought me down 11ms -> 6ms

foggy sphinx
#

😮 Now quite how the result climbs the ladder has me lost xD Going to need to stare at that for a lil bit for it to click.

nocturne sentinel
#

the "climbing" comes from the i+1 on the left side

foggy sphinx
#

I get that, but like. Right now I can't imagine what's happening with the bits. Need to think about it until I can picture that so it clicks.

And it's clicked. So you're also only needing to loop size-1 huh.

Feels pretty crazy. Ty for the lesson 8)

nocturne sentinel
#

;compile -std=c2x

#include <stdio.h>

int singleNumber(int* nums, int numsSize){
    for(int i = 0; i < numsSize - 1; i++) {
        printf("%03b ^ %03b = ", nums[i], nums[i+1]);
        nums[i+1] ^= nums[i];
        printf("%03b (%d)\n", nums[i+1], nums[i+1]);
    }
    return nums[numsSize - 1];
}

int main (void) {
    int nums[] = {4, 1, 2, 1, 2};

    singleNumber(nums, 5);
}
vapid gustBOT
#
Program Output
%03b ^ %03b = %03b (5)
%03b ^ %03b = %03b (7)
%03b ^ %03b = %03b (6)
%03b ^ %03b = %03b (4)
hisarya#0000 | 53ms | c | x86-64 gcc 13.2 | godbolt.org
nocturne sentinel
#

oh shoot no binary print extension on godbolt

#

(first line missing cause we don't have a 0 to start with)

timber obsidian
#

the basic insight is that if you XOR all the numbers together, the numbers that will appear twice will cancel each other out, leaving you with the single number

nocturne sentinel
#

you can expand that to the general case of "even frequencies get cancelled out"