CareerCup

Similar to Binary Search

public class KMEFinder {
	
	public int find(int[] sa, int k) {
		return find(sa, 0, sa.length-1, k, 0);
	}
	
	private int find(int[] sa, int stIdx, int endIdx, int k, int leftmisses) {
		if (endIdx - stIdx == 1) {
			return sa[stIdx]+(k - leftmisses);
		}
		
		int midIdx = stIdx + (endIdx-stIdx)/2;
		int lms = (sa[midIdx] - sa[stIdx]) - (midIdx - stIdx);
		if (leftmisses + lms >= k) {
			return find(sa, stIdx, midIdx, k, leftmisses);
		} else {
			leftmisses = leftmisses + lms;
			return find(sa, midIdx, endIdx, k, leftmisses);
		}
	}
}

def findMissingElement(arr,k):
mid = int (len(arr)-1)/2
mid = int(mid)+k
if arr[mid+1] - arr[mid] > 1:
return arr[int(mid)]+1
else:
return 0

public static int findK(int [] list, int num){
		 int k = 0, val = 0;
		 if(list.length < 2)return -1;
		 val = list[0];
		 for(int i = 0; i < list.length - 1; val = list[++i])
			 while((list[i + 1] - val++) > 1) 
				 if(k++ == num)return val;
		 return -1;
	 }

import java.util.Arrays;

public class MissingElement
{
  public static void main(String[] args)
  {
    int[] intArray = {2,3,5,7,8,9,11,12,13};
    int k = 3;
    System.out.println(missingK(intArray,k));
    
  }
    
  static int missingK(int[] arr, int k){
    int m = arr[1]-arr[0];
    int x = 0;
    int val = 0;
    do{
      for(int i=0;i<arr.length;i++){ 
        val = arr[i]+m;
        if(!contains(arr,arr[i]+m)){ 
          x++;
          if(k==x)break;
        }
      }
    }
    while(k!=x);
    return val;
  }
  
     public static boolean contains(final int[] array, final int v) {
        boolean result = false;
        for(int i : array){
            if(i == v){
                result = true;
                break;
            }
        }
        return result;
    }
}

public int findKthMissing(int[] arr, int k){
		return kthMissingHelper(arr, 0, arr.length-1, k);
	}
	
	public int kthMissingHelper(int[] arr, int low, int high, int k){
		int numRange = arr[high] - arr[low];
		int numPresent = high - low;
		int totalMissing = numRange - numPresent;
		if(totalMissing == 0)
			return arr[low] - 1;
		if(k > totalMissing)
			return -1;
		int middle = (low + high)/2;
		int missingCountInLeft = (arr[middle] - arr[low]) - (middle - low);
		if(missingCountInLeft >= k)
			return kthMissingHelper(arr, low, middle, k);
		else
			return kthMissingHelper(arr, middle+1, high, k - (missingCountInLeft));
	}

Ok, I missed the log(n) part last time, my bad. Following code uses binary search style solution and has log(n) average time. worst case is still O(n/2). For example when K = 0 and no K exists in the list.

static int FindK(int [] list, int K){
	 	if(list.length < 2)return -1;
	 	int d = list.length - 1;
		int m = d/2, dif = 0;
		
		while(d >= 0 && d < list.length){
			d = m;
			dif = (list[d] - list[0]) - d;
			if(K == dif){
				for(m = d; m < list.length - 1; m++)
					if(list[m + 1] - list[m] > 1)
						return ++list[d];
				break;
			}
			if(K < dif){
				m = d - (m + 1)/2;
			}else{
				m = d + (m + 1)/2;
			}
		}
		return -1;
	}

import org.junit.Test
import org.junit.Assert._

class Problem {
  def findMissingElement(array: Array[Int], target: Int, current: Int = 0): Option[Int] =
    if (current == (array.length - 1)) {
      None
    } else {
      val missingCount = array(current + 1) - array(current) - 1

      if (missingCount >= (target + 1)) {
        Some(array(current) + target + 1)
      } else {
        findMissingElement(array, target - missingCount, current + 1)
      }
    }

  @Test
  def test(): Unit = {
    val numbers = Array(2, 3, 5, 7)

    assertEquals(Some(4), findMissingElement(numbers, 0))
    assertEquals(Some(6), findMissingElement(numbers, 1))
    assertEquals(None, findMissingElement(numbers, 2))
    assertEquals(None, findMissingElement(numbers, 3))
  }
}

public void findNthMissingNum(int[] nums,int n){
        
        int low = 0;
        int high = nums.length - 1;

        while(low  < high){
            if(high - low == 1){
                System.out.println(nums[low]+n);
                break;
            }
            int mid = low + (high - low)/2;

            int missingOnLeft = nums[mid] - nums[low] - 1;
            int presentOnLeft = mid - low - 1;

            if(n > missingOnLeft - presentOnLeft){
                //go right
                low = mid;
                n -= missingOnLeft;
            }else{
                //go left
                high = mid;

            }

        }

}

public void findNthMissingNum(int[] nums,int n){
        
        int low = 0;
        int high = nums.length - 1;

        while(low  < high){
            if(high - low == 1){
                System.out.println(nums[low]+n);
                break;
            }
            int mid = low + (high - low)/2;

            int missingOnLeft = nums[mid] - nums[low] - 1;
            int presentOnLeft = mid - low - 1;

            if(n > missingOnLeft - presentOnLeft){
                //go right
                low = mid;
                n -= missingOnLeft;
            }else{
                //go left
                high = mid;

            }

        }
    }

int find(int arr[], int k) {
		int start = 0; 
		int end = arr.length-1;
		int count = 0;
		
		while (start <= end) {
			int mid = start + (end-start)/2;
			count = arr[mid] - arr[0] - mid;
			
			if(count >= k) {
				end = mid-1;
			}else 
				start = mid+1;
		}
		return arr[end] + k - (arr[end]-arr[0]-end);
	}

public class App7 {

    public static void main(String... arg) {

        System.out.println(countingSort(new int[]{1, 3, 4, 6, 7, 8,10,11,13}, 0, 0, 8));
        System.out.println(countingSort(new int[]{1, 3, 4, 6, 7, 8,10,11,13}, 1, 0, 8));
        System.out.println(countingSort(new int[]{1, 3, 4, 6, 7, 8,10,11,13}, 2, 0, 8));
        System.out.println(countingSort(new int[]{1, 3, 4, 6, 7, 8,10,11,13}, 3, 0, 8));

    }

    public static int countingSort(int[] arr, int k, int s, int e) {
        int mid = s + ((e - s) / 2);
        if (mid == s) {
            return arr[mid] + 1;
        }
        int i1 =   arr[mid]-((mid - s) + arr[s]);
        if (i1 >= (k + 1)) {
            return countingSort(arr, k, s, mid);
        } else {
            return countingSort(arr, k - i1, mid, e);
        }
    }
}

A simple python solution use list comprehensive.

def findMissing(alist, k):
	return [a for a in range(alist[0], alist[-1]+1) if a not in alist][k]

public class App7 {

    public static void main(String... arg) {

        System.out.println(countingSort(new int[]{1, 3, 4, 6, 7, 8,10,11,13}, 0, 0, 8));
        System.out.println(countingSort(new int[]{1, 3, 4, 6, 7, 8,10,11,13}, 1, 0, 8));
        System.out.println(countingSort(new int[]{1, 3, 4, 6, 7, 8,10,11,13}, 2, 0, 8));
        System.out.println(countingSort(new int[]{1, 3, 4, 6, 7, 8,10,11,13}, 3, 0, 8));

    }

    public static int countingSort(int[] arr, int k, int s, int e) {
        int mid = s + ((e - s) / 2);
        if (mid == s) {
            return arr[mid] + 1;
        }
        int i1 =   arr[mid]-((mid - s) + arr[s]);
        if (i1 >= (k + 1)) {
            return countingSort(arr, k, s, mid);
        } else {
            return countingSort(arr, k - i1, mid, e);
        }
    }
}