CareerCup

I could not find a way to resolve this question with the info provided without sorting the array/list first, and then finding the missing values from 1 - k-1 (assume MergeSort O(nLogn) followed by a scan of O(n)
Simply put, you cannot have an array of size K and the elements are 1-K-1
Example: K=5
Array {3,2,1,4, ??? } <-- It can't be 0 (>1), and it can't be 5 (<= k-1), and size of array = 4 not 5

Also, let's say that the OP did not write the question properly, and K is not the size of the array but the max value in the array
For example: {3,2,5,7}
Then K = 7 and the missing values are {1,4,6}. In this case, the array has to be scanned to get K, then processed to find missing values. 2*O(n)

Or let's say K is provided as input, then a valid input with K = 100 is array = {1}...
98 missing numbers.

Regardless, here's my solution that runs in 2*O(n). The assumptions I made:
1. K is provided is part of the input.
2. Missing elements are only one-apart from existing elements. For example
K = 13
Input is { 1,8,3,5,7,6,2,11,12}
Output would be {9,4,10}
I didn't test for edge cases by the way...

Code

public class FindMissing {

	private HashMap<Integer, Boolean> tracker;
	
	
	public List<Integer> findMissing(List<Integer> input, int K)
	{
		if(input == null) { throw new IllegalArgumentException();}
		this.tracker = new HashMap<>();
		//O(n)
		for(int i = 0; i < input.size();i++)
		{
			Integer current, previous, next;
			
			current = input.get(i);
			//Make sure we stay within the bounds of 1 - K-1
			if(current > 1)
				previous = current-1;
			else
				previous = null;
			if(current < K-1)
				next = current+1;
			else
				next = null;
			
			//Algorithm:
			//When inspecting an entry in the input list, if the entry doesn't exist, insert it with value true (found)
			//Check if the previous (-1) and next (+1) elements exist and insert with false, otherwise do nothing.
						
			if(tracker.containsKey(current) == false) //New entry.
			{
				tracker.put(current,true);
				if(previous != null)
				{
					if(tracker.containsKey(previous) ==false)
						tracker.put(previous, false);
				}
				if(next != null)
				{
					if(tracker.containsKey(next) == false)
						tracker.put(next, false);
				}
			}
			else //we have encountered this key before
			{
				tracker.put(current, true); //Update to 'found'
				
				if(previous != null)
				{
					if(tracker.containsKey(previous)==false) 
						tracker.put(previous, false); 
				}
				if(next != null)
				{
					if(tracker.containsKey(next)==false)
						tracker.put(next, false);
				}
				
			}
		}
		
		//Another O(n) to find the missing elements
		List<Integer> missing = new ArrayList<>();
		Iterator iter = tracker.entrySet().iterator();
		Map.Entry<Integer, Boolean> entry = null;
		while(iter.hasNext())
		{
			entry = (Entry<Integer, Boolean>) iter.next();
			if(entry.getValue() == false)
				missing.add(entry.getKey());
		}
		
		return missing;
		
		
	}

}

And the driver code

List<Integer> input = new ArrayList();
		input.add(1);
		input.add(8);
		input.add(3);
		input.add(5);
		input.add(7);
		input.add(6);
		input.add(2);
		input.add(11);
		input.add(12);
		
		FindMissing find = new FindMissing();
		List<Integer> missing = find.findMissing(input, 13); //K = 13, so elements are expected to be 1-12
		System.out.println(missing.toString());

what do you mean missing elements in array? maybe, missing elements in arithmetic progression?

counting sort can do this.

This post discusses 2 solutions: Sum and Xor.
capacode. com/array/find-missing-number-in-array/

This post discusses 2 solutions: Sum and Xor.
capacode. com/array/find-missing-number-in-array/

Can we use radix sort?

well, why not just substract the current int with the previous one (ie. n - (n-1))? if the diff is more than 1, there is one missing in between.

Sorry - thought that the array is sorted, if it is solution is way straightforward :)

def find_miss(a):
    k = len(a)
    ctr = 1
    seq = 1
    while(ctr < k):
        if(a[ctr] != seq):
            print(seq)
            seq = seq + 1
        ctr = ctr + 1
        seq = seq + 1
          

    
a = [0,1,2,3,5,7,8,9,11]
find_miss(a)

ok in theory if you know a1+a2+..ak, a1^ a1 + a2^a2 + a3^a3 +a4^a4+...ak^ak,.....
a1^k+....ak^k, you will get a1,a2....ak when you solve this equation in some way.
a1+....ak is n*(n+1)/2 - sum_of_array, a1^ a1 + a2^a2 + a3^a3 +a4^a4+...ak^ak is n*(n+1)*(2n+1)/6 - sum of cubes of array elements... sum of powers - there is a formule which convert to polinom of n - sum of k-th degree of array items
I personally prefer to avoid such calculation and to sort array with O(n) complexity.

def find_missing(l):
  l =sorted(l)
  min = l[0]
  max = l[len(l)-1]
  tmp = []
  while min<=max:
    tmp.append(min)
    min+=1
  return sorted(list(set(tmp) - set(l)))

void findMissingEle(int iArr[K])
{
	int resArr[K]={0};
	for(int i=0;i<K;i++)
		resArr[iArr[i]] =iArr[i];
	cout << "\n missing elements are :";
	for(int i=0;i<K;i++)
	{
		if(resArr[i]==0)
			cout << i ;
	}
}

It could be solved by counting sort:
1. find the min and max of the elements in the array
2. create any array of size max and init each element to 0
3. use counting sort to get the occurrence of elements in the array
4. check the new array from position min to max, the position of zero are the missing numbers

This is easy to do with a boolean array of size n. loop from i = 0 to n and anytime an element appears set that value to true. You can solve this problem for any arbitrary number of missing elements by scanning the array exactly once. It uses O(n) space and time.