Bit Manipulation Trick for Unique Element in Array

Day 70 of My DSA Journey Problem: Linked List Cycle (LeetCode 141) Today’s problem was all about detecting whether a linked list contains a cycle — a classic and very important concept in data structures. Key Idea: Floyd’s Cycle Detection Algorithm (Tortoise & Hare) Instead of using extra memory, we use two pointers: • Slow pointer → moves 1 step • Fast pointer → moves 2 steps If there’s a cycle, these two pointers will eventually meet. If not, the fast pointer will reach the end (null). Insight: This approach is efficient because it avoids using extra space like a HashSet and still guarantees detection in linear time. Complexity: • Time: O(n) • Space: O(1) What I learned: Sometimes, the smartest solutions don’t require extra space — just a clever observation and pointer manipulation! Consistency > Perfection 💯 On to Day 71 🚀 #DSA #100DaysOfCode #Java #CodingJourney #ProblemSolving #LinkedList

📘 DSA Journey — Day 26 Today’s focus: Binary Search fundamentals. Problems solved: • Binary Search (LeetCode 704) • Search a 2D Matrix (LeetCode 74) Concepts used: • Binary Search • Search space reduction • Index mapping in 2D arrays Key takeaway: In Binary Search, the idea is to repeatedly divide the search space in half. By comparing the target with the middle element, we eliminate half of the array each time, achieving O(log n) time complexity. In Search a 2D Matrix, the matrix can be treated as a flattened sorted array. Using index mapping: row = mid / cols col = mid % cols we can apply binary search directly on the matrix without extra space. These problems highlight how binary search is not limited to 1D arrays—it can be extended to structured data with proper transformations. Continuing to strengthen fundamentals and consistency in DSA problem solving. #DSA #Java #LeetCode #CodingJourney

🔥 Day 63 of #100DaysOfCode Solved – Missing Number 🔍 What I did: Calculated the expected sum of numbers from 0 to n and subtracted the actual sum of the array to find the missing number efficiently. 💡 Key Learning: Learned how to use mathematical formula (n × (n+1) / 2) Practiced optimizing from brute force to O(n) solution Improved understanding of number patterns in arrays 🎯 Takeaway: Using mathematical insights can simplify problems and eliminate the need for extra loops or space. #Day62 #LeetCode #Java #ProblemSolving #CodingJourney #100DaysOfCode #DSA

📘 DSA Journey — Day 35 Today’s focus: Binary Search with index patterns. Problem solved: • Single Element in a Sorted Array (LeetCode 540) Concepts used: • Binary Search • Index parity (even/odd pattern) • Search space reduction Key takeaway: The array is sorted and every element appears twice except one. A key observation: Before the single element, pairs start at even indices After the single element, this pattern breaks. Using binary search: • If mid is even and nums[mid] == nums[mid + 1], the single element lies on the right side • Else, it lies on the left side (including mid) By leveraging this pattern, we can find the answer in O(log n) time and O(1) space. Continuing to strengthen binary search intuition and consistency in problem solving. #DSA #Java #LeetCode #CodingJourney

🔥 Day 364 – Daily DSA Challenge! 🔥 Problem: 🎯 Find K Closest Elements Given a sorted array arr, an integer k, and a target x, return the k closest elements to x in ascending order. 💡 Key Insight — Binary Search on Window Instead of checking each element, we binary search the starting index of a window of size k. Search space: Possible windows → [0 ... n - k] 🧠 Decision Logic At index mid, compare: Distance of left boundary → x - arr[mid] Distance of right boundary → arr[mid + k] - x We choose direction based on: ⚡ Algorithm Steps ✅ Initialize: left = 0, right = n - k ✅ Binary search: If left side is farther → shift right Else → move left ✅ Final window starts at left ✅ Collect k elements ⚙️ Complexity ✅ Time Complexity: O(log(n - k) + k) (binary search + result building) ✅ Space Complexity: O(k) 💬 Challenge for you 1️⃣ Why do we search on window positions instead of elements? 2️⃣ Can you solve this using a heap approach? 3️⃣ What if array was unsorted? #DSA #Day364 #LeetCode #BinarySearch #SlidingWindow #Arrays #Java #ProblemSolving #KeepCoding

🔥 DSA Challenge – Day 136/360 🚀 📌 Topic: Bit Manipulation 🧩 Problem: Number of 1 Bits (Hamming Weight) Problem Statement: Given an integer, return the number of set bits (1’s) present in its binary representation. 🔍 Example: Input: 6 Output: 2 Explanation: Binary of 6 → 110 → 2 set bits 💡 Optimized Approach (Brian Kernighan’s Algorithm): Instead of checking each bit one by one, we use a smart trick: n & (n - 1) removes the rightmost set bit in each iteration This reduces the number of operations to the number of set bits only ⚡ Time Complexity: O(k) (k = number of set bits) ⚡ Space Complexity: O(1) 🚀 Key Takeaway: Using bit manipulation can drastically optimize performance compared to brute force approaches. Always look for patterns in binary operations! #DSA #Coding #Java #BitManipulation #136DaysOfCode #LeetCode #ProblemSolving #SoftwareEngineering

𝐃𝐚𝐲 𝟖𝟏 – 𝐃𝐒𝐀 𝐉𝐨𝐮𝐫𝐧𝐞𝐲 | 𝐀𝐫𝐫𝐚𝐲𝐬 🚀 Today’s problem focused on finding two unique numbers where all others appear twice. 𝐏𝐫𝐨𝐛𝐥𝐞𝐦 𝐒𝐨𝐥𝐯𝐞𝐝 • Single Number III 🔗 https://lnkd.in/dEQaaF3F 𝐀𝐩𝐩𝐫𝐨𝐚𝐜𝐡 – 𝐁𝐢𝐭 𝐌𝐚𝐧𝐢𝐩𝐮𝐥𝐚𝐭𝐢𝐨𝐧 (𝐎𝐩𝐭𝐢𝐦𝐚𝐥) Steps: • XOR all elements → gives a ⊕ b (two unique numbers) • Find rightmost set bit → differentiates a & b • Divide numbers into 2 groups based on that bit • XOR each group → get the two unique numbers 𝐊𝐞𝐲 𝐋𝐞𝐚𝐫𝐧𝐢𝐧𝐠𝐬 • XOR cancels duplicate elements • Bit tricks help split data into meaningful groups • Problems can often be optimized from O(n²) → O(n) • Understanding bit-level operations is very powerful 𝐂𝐨𝐦𝐩𝐥𝐞𝐱𝐢𝐭𝐲 • Time: O(n) • Space: O(1) 𝐓𝐚𝐤𝐞𝐚𝐰𝐚𝐲 When duplicates cancel out, think in terms of XOR and bit patterns. 81 days consistent 🚀 On to Day 82. #DSA #Arrays #BitManipulation #LeetCode #Java #ProblemSolving #DailyCoding #LearningInPublic #SoftwareDeveloper

💡 LeetCode 191 — Number of 1 Bits (Hamming Weight) Recently solved an interesting bit manipulation problem that highlights the power of low-level optimization 🚀 🔍 Problem Statement: Given an unsigned integer, count the number of set bits (1s) in its binary representation. 🧠 Key Insight: Instead of checking every bit individually, we can use a clever trick: 👉 n & (n - 1) removes the rightmost set bit in each operation. This allows us to count only the set bits, making the solution more efficient. ⚙️ Approach Used (Brian Kernighan’s Algorithm): Initialize a counter Repeatedly apply n = n & (n - 1) Increment count until n becomes 0 📈 Time Complexity: O(k), where k = number of set bits (faster than checking all 32 bits) 📦 Space Complexity: O(1) ✨ Why this problem is important: Strengthens understanding of bit manipulation Frequently asked in interviews Useful in low-level optimization and system design 💬 Takeaway: Sometimes the best solutions come from understanding how data is represented at the binary level. Small tricks can lead to big optimizations! #LeetCode #DSA #CodingInterview #Java #BitManipulation #ProblemSolving #TechJourney

🔥 DSA Challenge – Day 135/360 🚀 📌 Topic: Bit Manipulation 🧩 Problem: Check if a Number is Power of 2 Problem Statement: Given an integer n, determine whether it is a power of 2 or not. 🔍 Example: Input: n = 4 Output: true Input: n = 6 Output: false 💡 Approach: Optimized (Bit Manipulation) 1️⃣ Step 1 – If n <= 0, return false (powers of 2 are always positive) 2️⃣ Step 2 – Use bit trick: n & (n - 1) removes the lowest set bit 3️⃣ Step 3 – If result becomes 0, then only one set bit was present ✔ This avoids looping and works in constant time ⏱ Complexity: Time: O(1) Space: O(1) 📚 Key Learning: A number is a power of 2 if it has exactly one set bit in binary representation. #DSA #Java #Coding #InterviewPrep #ProblemSolving #TechJourney #135DaysOfCode #BitManipulation #LeetCode

Day 59/100 | #100DaysOfDSA 🔍⚡ Today’s problem: Single Element in a Sorted Array A clever Binary Search problem with a twist. Key observation: In a sorted array where every element appears twice except one, pairs follow a pattern. Before the single element: • First occurrence → even index • Second occurrence → odd index After the single element: • Pattern breaks Approach: • Use binary search • Check mid with its pair using index trick (mid ^ 1) • If nums[mid] == nums[mid ^ 1] → move right • Else → move left This helps pinpoint where the pattern breaks. Time Complexity: O(log n) Space Complexity: O(1) Big takeaway: Bit manipulation + pattern observation can simplify binary search problems significantly. Small tricks → big optimizations. 🔥 Day 59 done. #100DaysOfCode #LeetCode #DSA #Algorithms #BinarySearch #BitManipulation #Arrays #Java #CodingJourney #ProblemSolving #InterviewPrep #TechCommunity