mehraz
BAN USERwith a bit more complex data structure it can be solved in O(n) not o(n+k). however the space will be O(n+2k). we need to store the order of items in the hash map somehow.it can be done by having a hashMap<Integer, Node> evenNums as well as a linkedList. the hashMap points to the linked list. every time we see an even number we add it to the evenNums. if we see an odd num, we remove it from the even num (O(1) for updating the hash map and linkedlist). so the answer will be the first item in the linked list.
- mehraz January 05, 2016There is an O(n) solution. more accurately, O(32n) using bitwise operation.
the idea is behind a&b==a. What numbers have this characteristic?
Only those 'b' are acceptable that have exactly '1' at b[i] when a[i]=1. So, the rest of the bits can be either 1 or 0. If the rest of bits are all zero, then b is equal a (which is not acceptable). if any other bit is '1', then b will be greater than a.
Here is the algorithm:
int result = 0;
for( int d : array){
int noOfOnes = countOnes(d);
result+= Math.power(2, k- noOfOnes)-1; // reduce by one since a==b is not acceptable.
}
print(result);
In case of one missing number, the sum approach will solve the problem.
If there are multiple missings in different locations, then we can solve it in time O(2*n) and space O(1):
- run one iteration to find the minimum difference between the numbers. the min would be 'd'.
- run the second iteration, and detect the missing numbers between each two items in the array. E.g., if a[i]-a[i-1] == d*3, then it means there are 2 numbers missing between i and i-1.
Nice solution. Just note that if we use combination of hashmap and linked lists (like what we do for implementing LRU) for storing the position of character that we say, then the space will be O(2k) which is will be smaller (equal if k is 128) than your solution
- mehraz December 18, 2015**It can be done in O(n) and space O(1).**
we need to scan 3 times through the array and change some values carefully.
Assumption: the max value in the array with size N is should be smaller than (N+1) * Interger.MAX_VALUE.
We need this assumption since we well change some positive values in the array.
- in the first scan, find # of negative and positive values, and the max.
- in the second scan we create the negative section of array as follows:
we start from the beginging of the array and we "**swap**" the first found positive number (e.g. at index i) with the first found negative number (e.g. j). since negative number are being considered with respect to their location, the swap will be okay. the problem is the positive numbers because there might be some other positive numbers between i and j. To handle this issue, we have to somehow encode the index of the positive number in that value before swaping. so then we can realize where it was at the first point. we can do this by a[i]=(i+1)*(max)+a[i].
- in the third scan, we create the positive section of array. by end of the second scan, the negative array is constructed, and the positive numbers are shifted to the right side, but their location may not be correct. So we go though it and correct their position since this info was encoded their value.
Here is the code:
import java.util.Arrays;
public class LinearShifting {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] a = {-1,7,3,-5,4,-3,1,2};
sort(a);
System.out.println(Arrays.toString(a)); //output: [-1, -5, -3, 7, 3, 4, 1, 2]
}
public static void sort(int[] a){
int pos = 0;
int neg = 0;
int i,j;
int max = Integer.MIN_VALUE;
for(i=0; i<a.length; i++){
if(a[i]<0) neg++;
else pos++;
if(a[i]>max) max = a[i];
}
max++;
if(neg==0 || pos == 0) return;//already sorted
i=0;
j=1;
while(true){
while(i<=neg && a[i]<0) i++;
while(j<a.length && a[j]>=0) j++;
if(i>neg || j>=a.length) break;
a[i]+= max*(i+1);
swap(a,i,j);
}
i = a.length-1;
while(i>=neg){
int div = a[i]/max;
if(div == 0) i--;
else{
a[i]%=max;
swap(a,i,neg+div-2);// minus 2 since a[i]+= max*(i+1);
}
}
}
private static void swap(int[] a, int i , int j){
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}
The brute force solution would be add each number to its related linked list. Since insertion can take O(n), the total complexity would be O(n^2). One way to reduce the complexity is to reduce the insertion time. Since it is doubly linked list, we can have a BST fo each even and odd numbers, instead. We can later convert the BST to doubly linked list in O(n) in place. So,the total complexity would be O(nlogn) and space O(n).
- mehraz February 17, 2016