Searching an array recursively - CodingBat

Question

Apologies for the ambiguous title, I could not think of something more specific.

In order to get better at solving problems recursively, I have been tackling the questions posted on CodingBat. My question is related to a variation of the following problem.

The original problem is:

Given an array of ints, compute recursively if the array contains somewhere a value followed in the array by that value times 10. We'll use the convention of considering only the part of the array that begins at the given index. In this way, a recursive call can pass index+1 to move down the array. The initial call will pass in index as 0.

• array220({1, 2, 20}, 0) → true
• array220({3, 30}, 0) → true
• array220({3}, 0) → false

My solution to this problem is:

public boolean array220(int[] nums, int index) {
  if (index >= nums.length-1) return false;

  if (nums[index+1] == nums[index] * 10) return true; 

  return array220(nums, ++index);
}

However, in order to challenge myself, I was wondering how I would go about solving the following variation of this problem that I conceived:

Given an array of ints, compute recursively if the array contains somewhere a value that is 10 times larger than any other value. We'll use the convention of considering only the part of the array that begins at the given index. In this way, a recursive call can pass index+1 to move down the array. The initial call will pass in index as 0.

For example:

• array220({1, 2, 10}, 0) → true
• array220({3, 2, 9, 38, 20}, 0) → true
• array220({3}, 0) → false

So basically, the difference with the original problem is that the values may not necessarily be adjacent to one another (see examples above).

How would I go about doing this recursively? I would appreciate some pointers.

I do not want to change the method signature or use global variables.

Answer 1

This can be the answer, just making use of a HashSet, and passing it along when you make recursive call:

public boolean array220(int[] nums,HashSet<Integer> set,  int index) {
  if (index >= nums.length-1) return false;

  if (set.contains(nums[index]*10)) 
      return true; 
  set.add(nums[index]);
  return array220(nums,set, ++index);
}

If you don't want to use additional data structures, sorting array and making use of binary search can bring you an O(nlogn) solution, with two recursive methods.

Arrays.sort(nums);

public boolean array220(int[] nums,  int index) {
  if (index >= nums.length-1) return false;

  if (binarySearch(index + 1, nums.length - 1,nums[index]*10,nums)) 
      return true; 

  return array220(nums, ++index);
}

public boolean binarySearch(int start, int end,int value, int[] nums){
     if(start > end)
        return false;
     int mid = (start + end)/2;
     if(nums[mid] == value){
         return true;
     }else if(nums[mid] > value){
         return binarySearch(start, mid - 1, value, nums);
     }else{
         return binarySearch(mid + 1, end, value, nums);
     } 
}

If you don't want to sort the array, using a linear recursive search will give a O(n^2) solution.

public boolean array220(int[] nums,  int index) {
  if (index >= nums.length-1) return false;

  if (linearSearch(0,nums[index]*10,nums)) 
      return true; 

  return array220(nums, ++index);
}

public boolean linearSearch(int start, int value, int[] nums){
     if(start >= nums.length)
        return false;

     if(nums[start] == value){
         return true;
     }else {
         return linearSearch(start + 1, value, nums);
     } 
}