Recursive algorithm problem(missing number)

user_16639876 0
Viewed 422

So I have an array A[1:n] which contains random unique numbers from 1 to n+1(including n+1). The task is to find the missing number. Usually you just make an additional array B[1:n+1] and mark each present number in array A as 1 in array B. BUT in this problem you each number in array A is given in binary code as a string and I can access elements of A only by j-th symbol in a i-th string The goal is to come up with an algorithm with complexity O(n)

My ideas: I came up with a merge sort based algorithm, which would sort every string according its first number in binary code. But the complexity is O(nlgn)

recursion time-complexity arrays algorithm
3 Answers

As discussed in the comments, if elements of A can only be accessed bit-by-bit then no O(n) solution is going to be possible, since all bits have to be read, and there are log n bits in each number. The best that can be done is O(n log n).

That said, if the array contains n elements from the range 1 to n+1, with exactly one value missing, the missing value can be found by taking the sum of the array and comparing it to the sum to n+1, given by the standard formula, (n+1)(n+2)/2.

int n = 3;
String[] arr = {"001", "010", "100"};

int sum = 0;
for(int i=0; i<arr.length; i++) 
    for(int j=0, v=1; j<arr[i].length(); j++, v*=2)
        if(arr[i].charAt(j) == '1') sum += v;

int m = (n+1)*(n+2)/2 - sum;

System.out.println("Missing: " + m);

Output:

Missing: 3
user_64388190

Here's a working implementation in Ruby using built-in binary conversion. I've commented it enough that I don't think additional verbiage is required for explanation. Notice that ordering of the binary strings is not necessary for this to work.

ary = ["1", "010", "100", "110", "11"]  # Works with or without leading zeros
n_plus_1 = ary.size + 1
result = n_plus_1 * (n_plus_1 + 1) / 2  # Total if all values were present

# Convert each string in ary to int using base 2, and deduct from the total
ary.each { |str| result -= str.to_i(2) }

# The remainder is the missing value
puts "Missing value is #{result} (binary #{result.to_s(2)})"

Both that and the code below produce the following output:

Missing value is 5 (binary 101)

If you want to avoid built-in conversion, here it is with a recursive converter which should be straightforward to translate to other languages. Note that Ruby method arguments given a default value don't need to be provided explicitly in the method call:

def str_to_i(char_ary, power = 1, radix = 2)
  return 0 if char_ary.size == 0  # Base case
  bit = char_ary.pop.to_i  # Remove last character in array and convert to int
  return bit * power + str_to_i(char_ary, power * radix, radix)
end

ary = ["1", "010", "100", "110", "11"]  # Works with or without leading zeros
n_plus_1 = ary.size + 1
result = n_plus_1 * (n_plus_1 + 1) / 2  # Total if all values were present

# Convert each string to array of chars, then to int, and deduct from total
ary.each { |str| result -= str_to_i(str.chars) }

# The remainder is the missing value
puts "Missing value is #{result} (binary #{result.to_s(2)})"

This also fulfills your use of the recursion tag.

If you want to do the full Monty on recursion:

def str_to_i(char_ary, power = 1, radix = 2)
  return 0 if char_ary.size == 0  # Base case
  bit = char_ary.pop.to_i  # Remove last character in array and convert to int
  return bit * power + str_to_i(char_ary, power * radix, radix)
end

# Assuming String -> Integer can be considered O(1):
#   T(n) = 2 * T(n/2) + O(1) => O(n)
# Stack size is O(log n), which should avoid stack overflow, where splitting
# array into subsets of 1 an n-1 would exceed recursive stack limits even for
# relatively small arrays (more than a few hundred).
def sum_array(ary, first = 0, last = ary.size - 1)
  # return ary[first].to_i(2) if last == first  # using built-in conversion
  return str_to_i(ary[first].chars) if last == first  # avoiding built-in
  mid = first + (last - first) / 2
  return sum_array(ary, first, mid) + sum_array(ary, mid + 1, last)
end

ary = ["1", "010", "100", "110", "11"]  # Works with or without leading zeros
n_plus_1 = ary.size + 1
result = n_plus_1 * (n_plus_1 + 1) / 2 - sum_array(ary)    

# The remainder is the missing value
puts "Missing value is #{result} (binary #{result.to_s(2)})"
user_21667980

You can use the fact that

XOR({1,..,4n-1})=0

and so, if one of the elements is missing, XOR({1,..,4n-1}-{k})=k,

by adding any necessary dummy elements to your given array.

user_43619990
Related