IB
BAN USERWe just want to find the duplicates. We can walk on the array and put every element in the the corresponding index. If we find two elements in same position, we insert them into a set<in> as the final results.
O(1) Space, O(n) time
int main()
{
// std::vector<int> inp = {4, 2, 0, 5, 2, 0, 1} ;
std::vector<int> inp = {1, 2, 3, 0, 0, 1, 3, 6, 6,6};
//It is only for holding output
// You can print the results instead of inserting here.
std::set<int> res;
for(int i = 0; i < inp.size(); i++){
if(inp[i] == i) continue;
if(inp[inp[i]] == inp[i]) res.insert(inp[i]);
else{
auto temp = inp[inp[i]];
inp[inp[i]] = inp[i];
inp[i] = temp;
i--;
}
}
for(set<int>::iterator it = res.begin(); it != res.end(); it++)
cout << *it << " ";
return 0;
}
I should add that if you don't want to even reserve space for the output variable, you can print the duplicates as soon as you see them first. But in order to not print them more than once, after printing any duplicated, we can make them to -1 and be sure that we will not print them twice.
- IB May 08, 2017An O(n^2) solution which helps to understand the idea. It can get improved.
int main() {
vector<int> r;
r.push_back(13);
r.push_back(1);
r.push_back(1);
r.push_back(2);
r.push_back(3);
int maxNum = 0;
for(int i = 0 ; i < r.size(); i++){
int tempMax = 0;
for(int j = 0 ; j < r.size(); j++){
if(abs(r[i] - r[j]) <= abs(i-j)) tempMax++;
}
maxNum = max(maxNum, tempMax);
}
cout << "Max Number: " << maxNum << endl;
}
Here is a simple python code:
def bitOp(A,B):
for t in A:
if t == '1':
break;
A = A[1:]
for t in B:
if t == '1':
break;
B = B[j:];
aa, bb = 0,0;
for t in A:
aa = ((aa<<1) + 1) if t == '1' else aa<<1;
for t in B:
bb = ((bb<<1) + 1) if t == '1' else bb<<1;
return aa + bb;
Here is a python code. It is a recursive function. If we have "abc", it calls the recursive function three times.
1- prefix = a; str = ''bc"
2- prefix = b; str = ''ac"
3- prefix = c; str = ''ab"
def prm(prefix, str):
if len(str) == 1:
print prefix + str;
return;
for i in range(len(str)):
temp = str[:i] + str[i+1:];
prm(prefix+str[i], temp)
@ChrisK
- IB May 08, 2017In this case, I wanted to say that we can mark the duplicates by -1, and then saw your code. sounds cool.