1+ /*
2+ * Problem: 268
3+ * Name: Missing Number
4+ * Difficulty: Easy
5+ * Topic: Bit Manipulation
6+ * Link: https://leetcode.com/problems/
7+ */
8+
9+ #include < bits/stdc++.h>
10+ using namespace std ;
11+
12+ // Binary Search
13+ /* When the n numbers are ordered, if the number at index i is equal to i,
14+ * then all number before it are in the correct positions, so the lowerBound
15+ * can be incremented; otherwise, there is a number missing before i, and the
16+ * upperBound should be decremented
17+ * Eventually they will converge to the index/value missing and return it
18+ */
19+ // Time Complexity: O(n log n)
20+ // Space Complexity: O(1)
21+ int missingNumberSort (vector<int >& nums) {
22+ sort (nums.begin (), nums.end ());
23+ int lowerBound = 0 ;
24+ int upperBound = nums.size ();
25+ while (lowerBound < upperBound){
26+ int midValue = lowerBound + (upperBound - lowerBound) / 2 ;
27+ if (nums[midValue] > midValue){
28+ upperBound = midValue;
29+ }
30+ else {
31+ lowerBound = midValue + 1 ;
32+ }
33+ }
34+ return lowerBound;
35+ }
36+
37+ // Sum of the sequence
38+ /* Using the gaussian formula for the sum of the first n values of a sequence
39+ * we can obtain the total sum of the sequence and iterate through the loop
40+ * subtracting the numbers that are there, the result will be the missing number
41+ */
42+ // Time Complexity: O(n)
43+ // Space Complexity: O(1)
44+ int missingNumberMath (vector<int >& nums) {
45+ int result = ((nums.size ()+1 ) * (0 + nums.size ())) / 2 ;
46+ for (const int &n : nums){
47+ result -= n;
48+ }
49+ return result;
50+ }
51+
52+ // Bit Manipulation (XOR)
53+ // Time Complexity: O(n)
54+ // Space Complexity: O(1)
55+ int missingNumber (vector<int >& nums) {
56+ int result = nums.size ();
57+ for (int idx = 0 ; idx < nums.size (); idx++){
58+ result ^= idx;
59+ result ^= nums[idx];
60+ }
61+ return result;
62+ }
0 commit comments