CODEWITHSUNDEEP
javaalgorithmbinary-search
DESI RECORDS
DESI RECORDS

Reputation: 37

Using binary search for finding the number that appears odd number of times in an array of numbers

I am able to do it for my first example but for example 2, I am not able to get the right answer. My code actually looks for the middle position and traverse the array to the right side of the array as mid -1 = mid, which makes the condition true but mid -1 = mid -2. What should I do for ignoring this? 

 import java.util.Arrays;

class Lab4 {
// Function to return k'th smallest
// element in a given array


public static int findOddNumber(int[] numbers, int startIndex, int endIndex) {

    int mid = 0;
    mid = (startIndex + endIndex) / 2;

    if (startIndex == endIndex) {
        return numbers[startIndex];
    }
    if (mid % 2 == 0) {
        if (numbers[mid] == numbers[mid + 1]) {
            return findOddNumber(numbers, mid + 2, endIndex);
        } else {
            return findOddNumber(numbers, startIndex, mid);
        }
    } else {
        if (numbers[mid] == numbers[mid - 1])
            return findOddNumber(numbers, mid + 1, endIndex);
        else
            return findOddNumber(numbers, startIndex, mid - 1);
    }
}

// driver program
public static void main(String[] args) {


    int arr2[] = new int[] { 1, 1, 2, 3, 3, 5, 5 };
    System.out.println("Odd number is " + findOddNumber(arr2, 0, arr2.length - 1));

    int arr3[] = new int[] { 1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 6, 6 };
    System.out.println("Odd number is " + findOddNumber(arr3, 0, arr3.length-1));

    }

}

Upvotes: 0

Views: 1442

Answers (3)

maraca
maraca

Reputation: 8753

Sorry I understand your solution now. One of the problems is that just by looking at the element to the right or the left of mid you still can't know which way to go. So here is an adaption: Find the last index with the same value as the value for mid using binary search. If it is odd, then you have to search in the subarray right of that index, otherwise you have to look on the left side. Time complexity O((logn)^2), but only works for ordered arrays with exactly one element appearing an odd number of times. In code:

public static int findOddNumber(int[] numbers, int startIndex, int endIndex) {
    if (numbers[startIndex] == numbers[endIndex])
        return numbers[startIndex];
    int mid = (startIndex + endIndex) / 2;
    int last = findLast(numbers, mid, endIndex);
    if (last % 2 == 1)
        return findOddNumber(numbers, last + 1, endIndex);
    else
        return findOddNumber(numbers, startIndex, mid - mid % 2);
}

private static int findLast(int[] numbers, int startIndex, int endIndex) {
    if (numbers[startIndex] == numbers[endIndex])
        return endIndex;
    int mid = (startIndex + endIndex) / 2;
    if (numbers[startIndex] == numbers[mid])
        return findLast(numbers, mid, endIndex - 1);
    else
        return findLast(numbers, startIndex, mid - 1);
}

For unordered arrays there are much simpler ways to find all the odd numbers using a hash set. This also works for multiple odd numbers. Just go through the array and if a number is already in the set remove it otherwise add it. In the end you have all numbers that appear an odd number of times in the hash set. This takes O(n) time and space.

If you know that there is exactly one number appearing an odd number of times, then you can just xor all the array values and get the solution. O(n) time and O(1) space. This also works for unordered arrays.

Upvotes: 3

Joop Eggen
Joop Eggen

Reputation: 109577

A binary search is possible by the length of subranges.

One has to ensure that the subranges come from splitting a range such that the second subrange starts with a different value as the first ends with.

Your solution did not loop for splitting. Also the oddness of the length of the subrange, not the mid index must be checked.

public static int findOddNumber(int[] numbers) {
    return findOddNumber(numbers, 0, numbers.length);
}

with a recursive binary splitting:

/**
 * @param numbers where only one value occurs an odd number of times.
 * @param startIndex.
 * @param endIndex exclusive.
 */
public static int findOddNumber(int[] numbers, int startIndex, int endIndex) {
    assert endIndex - startIndex % 2 == 1;

    if (endIndex - startIndex == 1) {
        return numbers[startIndex];
    }
    // Now at least two elements.

    // Try to split into two subranges, the first ending with a different value
    // as the second subrange.
    int mid = (startIndex + endIndex) / 2;

    // Do not split inside subrange of the same number:
    int split = mid + 1;
    while (split < endIndex && numbers[split] == numbers[split - 1]) {
        ++split;
    }
    if (split == endIndex) {
        split = mid;
        while (split > startIndex && numbers[split] == numbers[split - 1]) {
            --split;
        }
    }
    if (split == startIndex || split == endIndex) { // Could not split.
        return numbers[startIndex]; // All numbers the same.
    }
    if ((split - startIndex) % 2 == 1) {
        return findOddNumberIndex(numbers, startIndex, split);
    } else {
        return findOddNumberIndex(numbers, split, endIndex);
    }
}

Now the split could use a binary search (Arrays.binarySearch) to find begin and end, by searching numbers[mid] + or - 0.5 but that is not feasible here.

As curiosity an alternative solution, when the numbers are not ordered:

public static int findOddNumber(int[] numbers) {
    int result = 0;
    for (int n : numbers) {
        retult ^= n;
    }
    return n;
}

This utilizes x^x == 0 and 0^x == x. ^ (XOR) being commutative and associative.

Upvotes: 0

Manish Sharma
Manish Sharma

Reputation: 142

Assuming that it's a sorted array, the best "worst case time complexity" you can get is O(n). It is so because the worst case scenario is when all the elements in the array are different and occur just once each. (For example -> 1,2,3,4,5)

And the O(n) time complexity and O(1) space complexity solution would be to iterate through the array with a curr_element (Storing the curr_element which might be repeating), a count variable(To count occurences of curr_element) and a total variable(answer to the question) extra. Iterate, count occurences of curr_element and if it is odd, increment total.

There can't be any solution better than O(n) in this case.

Upvotes: 0

Related Questions