1

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.

Improve this question
12
  • 1
    This is not really a recursive problem, even in its first version. However, an iterative algorithm can always be converted in a tail-recursive algorithm, so you can just write your hastable solution in a recursive fashion Commented Jan 21, 2015 at 2:40
  • @Dici the problems posted on CodingBat are meant to be solved only using recursion. I am doing this for practice. How would I go about doing this recursively without using a data structure? It appears I need a way to do a nested loop. Commented Jan 21, 2015 at 2:44
  • Similar to how you do in original version, just add an additional Hash Table as a parameter in recursive method. Commented Jan 21, 2015 at 2:45
  • 1
    @sparrow the whole purpose of this activity is to practice recursion. The problems on CodingBat are designed to be solved without loops. Please read the problem carefully. Efficiency or elegance is not of relevance to this question. Commented Jan 21, 2015 at 2:46
  • @PhamTrung how would I go about doing this recursively without the use of additional data structures? Could you provide some pseudocode? Commented Jan 21, 2015 at 2:47

1 Answer 1

Reset to default
2

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);
     } 
}
Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

How can we do it without the use of a data structure? I am not concerned about efficiency. I do not want to change the method signature or use any global variables.
@gentleArt, look at the second and third solution, the solution doesn't require additional datastructure
Could you clarify the following boolean condition: (nums[index] % 10 == 0 && linearSearch(0,nums[index]/10,nums)) I am not quite sure what this is doing? Is it checking for 0? Thank you!
@gentleArt nums[index] % 10 == 0 means that whether the current nums[index] is divided by 10, for example: 10, 20, 30,... if it is, so we need to find 1, 2, 3..., which is nums[index]/10
@gentleArt hmm, that part is not necessary, just remove that part

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.