LeetCode Problem 287: Duplicate Number Solution

Problem 287, Find the Duplicate Number on LeetCode, is probably the most unintuitive medium question I’ve ever encountered. I spent around 30 minutes just reading and fully understanding the question, and I still had to draw diagrams and write out a quick proof to convince myself why the solution always works. After that, the implementation was basically around 7 lines of code (if you ignore spacing and use some fancier Python formatting). Despite the hassle, it was a really satisfying “aha” moment, recognizing the linked-list cycle pattern in a problem that doesn’t even use linked-list nodes. #SoftwareEngineering #LeetCode #Coding #Programming

  • No alternative text description for this image

Isn’t this the toetoise and the hare problem

Like
Reply

Haha, you are easily satisfied, slightly bored and extremely capable 😀😀😀

Like
Reply

The face says it all.

Like
Reply

Welcome to brain gym. 😀

Like
Reply

There’s an xor trick here I just know it. The closest I can think of is if you sum the array and xor every value in the array into one number then do sum - xor you’d be left with the value that was repeated, but something in the back of my head is saying there’s a way to do it with just the xor value.

Maybe I'm missing something but why not reserve a 10^5 sized array and for each value just turn the corresponding index on unless it already is? If it is, that's the answer. Doesn't need to modify the original, uses constant space & linear runtime complexity.

Like
Reply

Love when a problem hides a pattern like that. Those “wait… this is secretly cycle detection?” moments are the best kind of brain reward.

Like
Reply

The Tortoise and the Hare Algorithm? More like the rip out my hair algorithm 😂 this is a tough one, nice job!

Welcome To Leetcode Buddy 🤣

Like
Reply
See more comments

To view or add a comment, sign in

Explore content categories