Monday, 8 October 2018

FindMissing number in AP log(n)

public class FindMissing {

    public static void main(String[] args) {
        int[] arr = {2,4,6,8,12,14,16,18,20,22,24,26};
        int val = findMissing(arr, 0, arr.length-1, 2);
        System.out.println(val);
    }
   
   
    static int findMissing(int[] arr, int start, int end,int diff) {
        if (end >= start) {
            int mid = (start + end) / 2;
            if (mid<end && (arr[mid+1] - arr[mid]) != diff) {
                return arr[mid] + diff;
            } else if (mid>0 && (arr[mid] - arr[mid-1]) != diff) {
                return arr[mid-1] + diff;
            }
//if difference in left and right element of mid are equal to diff then we need to decide to move either //left or right as we will check if our series is correct till mid then we will move to right otherwise left
//for checking till mid series  is correct we will use formula : arr[mid]==arr[0]+mid*diff


else if (arr[mid] == arr[0] + mid * diff) {
                return findMissing(arr, mid + 1, end, diff);
            } else {
                return findMissing(arr, start, mid - 1, diff);
            }

        }
        return 0;
    }

}

No comments:

Post a Comment

links for Data Structure

  1) 𝐁𝐞𝐜𝐨𝐦𝐞 𝐌𝐚𝐬𝐭𝐞𝐫 𝐢𝐧 𝐋𝐢𝐧𝐤𝐞𝐝 𝐋𝐢𝐬𝐭:  https://lnkd.in/gXQux4zj 2) 𝐀𝐥𝐥 𝐭𝐲𝐩𝐞𝐬 𝐨𝐟 𝐓𝐫𝐞𝐞 𝐓𝐫𝐚𝐯𝐞𝐫𝐬𝐚𝐥𝐬...