idx is the element of the array. For instance- idx = abs(arr[i]) We want to mark the presence of 'idx' in the array. The way we are marking this is by marking the index indicated by idx as negative. For example- if the array is [2, 1, 4, 1, 1, 1] and if idx = 2 Then we want to mark the presence of idx(idx=2) in the array. The way we are achieving this is by negating arr[id-x]. So, in this case after manipulation of idx=2, the array will look something like this- [2, 1, -4, 1, 1, 1]. Hope this helps!
class Solution { public: // Function to find the smallest positive number missing from the array. int missingNumber(vector &arr) { bool flag = false; int n = arr.size(); for (int i = 0; i < n; i++) { if (arr[i] == 1) flag = true; if (arr[i] < 1 or arr[i] > n) arr[i] = 1; } if (not flag) return 1; for (int i = 0; i < n; i++) { int id = abs(arr[i]); arr[id - 1] = -1*abs(arr[id-1]); } for (int i = 0; i < n; i++) { if (arr[i] > 0) return i + 1; } return n + 1; } };
class Solution: #Function to find the smallest positive number missing from the array. def missingNumber(self,arr): flag = False n = len(arr) for i in range(n): if arr[i] == 1: flag = True if arr[i] < 1 or arr[i] > n: arr[i] = 1 if not flag: return 1 for i in range(n): idx = abs(arr[i]) arr[idx - 1] = -1*abs(arr[idx - 1]) for i in range(n): if arr[i] > 0: return i + 1 return n + 1
Nice explanation
Table of Contents
0:00 Problem Statement
0:33 Solution
7:45 Pseudo Code
10:15 Code - Python
11:11 Code - C++
Sir. What is idx?
Why should we use modulus?
I mean converting positive integer into the negative ones
idx is the element of the array. For instance-
idx = abs(arr[i])
We want to mark the presence of 'idx' in the array. The way we are marking this is by marking the index indicated by idx as negative. For example-
if the array is [2, 1, 4, 1, 1, 1] and if idx = 2
Then we want to mark the presence of idx(idx=2) in the array. The way we are achieving this is by negating arr[id-x]. So, in this case after manipulation of idx=2, the array will look something like this-
[2, 1, -4, 1, 1, 1].
Hope this helps!
class Solution {
public:
// Function to find the smallest positive number missing from the array.
int missingNumber(vector &arr) {
bool flag = false;
int n = arr.size();
for (int i = 0; i < n; i++) {
if (arr[i] == 1)
flag = true;
if (arr[i] < 1 or arr[i] > n)
arr[i] = 1;
}
if (not flag)
return 1;
for (int i = 0; i < n; i++) {
int id = abs(arr[i]);
arr[id - 1] = -1*abs(arr[id-1]);
}
for (int i = 0; i < n; i++) {
if (arr[i] > 0)
return i + 1;
}
return n + 1;
}
};
class Solution:
#Function to find the smallest positive number missing from the array.
def missingNumber(self,arr):
flag = False
n = len(arr)
for i in range(n):
if arr[i] == 1:
flag = True
if arr[i] < 1 or arr[i] > n:
arr[i] = 1
if not flag:
return 1
for i in range(n):
idx = abs(arr[i])
arr[idx - 1] = -1*abs(arr[idx - 1])
for i in range(n):
if arr[i] > 0:
return i + 1
return n + 1