Also find the missing number?.Your algorithm should run in o(n) and o(1) time.
Best solution so far:Time - o(n) space - o(1).No need to sum the array.No equations. No change in content of array.Solution:for(int i = 0; i < n;i++){ a[ |a[i]| ]*= (-1);//Now only two array index must be //positive, one is missing and //other is repeated.int n1=-1,n2=-1;for(int i=0;i 0){ if( n1 == -1){ n1 = a[i]; } else{ n2 = a[i]; } }else{ a[i]*=(-1); } }// n1 and n2 are repeated and //misssing numbersfor(int i=0;i<n;i++){ if( n1 == a[i]){ count++; }}if( count == 2){ n1 is repeated, n2 is missing}else{ n2 is repeated, n1 is missing.}
Also find the missing number?.
ReplyDeleteYour algorithm should run in o(n) and o(1) time.
Best solution so far:
ReplyDeleteTime - o(n) space - o(1).
No need to sum the array.
No equations.
No change in content of array.
Solution:
for(int i = 0; i < n;i++){
a[ |a[i]| ]*= (-1);
//Now only two array index must be //positive, one is missing and //other is repeated.
int n1=-1,n2=-1;
for(int i=0;i 0){
if( n1 == -1){
n1 = a[i];
}
else{
n2 = a[i];
}
}else{
a[i]*=(-1);
}
}
// n1 and n2 are repeated and //misssing numbers
for(int i=0;i<n;i++){
if( n1 == a[i]){
count++;
}
}
if( count == 2){
n1 is repeated, n2 is missing
}else{
n2 is repeated, n1 is missing.
}