Java Algorithm Question

Problem Statement :: In Java ,Given an array of ints, is it possible to choose a group of some of the ints, such that the group sums to the given target, with this additional constraint: if there are numbers in the array that are adjacent and the identical value, they must either all be chosen, or none of them chosen. For example, with the array {1, 2, 2, 2, 5, 2}, either all three 2's in the middle must be chosen or not, all as a group. (one loop can be used to find the extent of the identical values).

 groupSumClump(0, {2, 4, 8}, 10) → true      
 groupSumClump(0, {1, 2, 4, 8, 1}, 14) → true                   
 groupSumClump(0, {2, 4, 4, 8}, 14) → false --> Failing Test Case               
 groupSumClump(0, {8, 2, 2, 1}, 9) → true   --> Failing Test Case      
 groupSumClump(0, {8, 2, 2, 1}, 11) → false --> NegativeArraySizeException 

I have done some initial Analysis and the partial code is as below.

  publ开发者_运维问答ic boolean groupSumClump(int start, int[] nums, int target) {
    start = 0;
    boolean flag = false;

    // get the highest int from the list of array we have
    int highestInteger = getTheBiggest(nums);
    if (highestInteger > target) {
        flag = false;
    } else {
        int variable = 0;
        for (int i = 0; i < nums.length; i++) {
            variable += nums[i];
        }
        if (variable == target) {
            flag = true;
        } else {
            if (variable < target) {
                flag = false;
            } else {
                // here goes ur grouping logic here
                flag = summate(highestInteger, target, nums);
            }
        }
    }

    return flag;
}

private  boolean summate(int highestInteger, int target, int[] nums) {
    boolean val = false;
    if (highestInteger == target) {
        val = true;
    } else {
        int[] temp = new int[nums.length - 1];
        int var = 0;            

        if ((target - highestInteger) > 0) {
                 for (int j = 0; j < nums.length-1; j++) {
                   if (nums[j] != highestInteger) {
                     temp[var] = nums[j];
                     if (temp[var] == (target - highestInteger)) {
                        val = true;
                        return val;
                     }
                     var++;
                   }
                 }
             val = summate(getTheBiggest(temp), target - highestInteger,
                     temp);  

         }                                      
     }      
    return val;
}

private int getTheBiggest(int[] nums) {
    int biggestInteger = 0;
    for (int i = 0; i < nums.length; i++) {
        if (biggestInteger < nums[i]) {
            biggestInteger = nums[i];
        }
    }
    return biggestInteger;
}

Please Note: I dont know how to handle the logic for below problem statement : There is an Additional Constraint to the problem such that if there are numbers in the array that are adjacent and the identical value, they must either all be chosen, or none of them chosen. For example, with the array {1, 2, 2, 2, 5, 2}, either all three 2's in the middle must be chosen or not, all as a group. (one loop can be used to find the extent of the identical values).

how should i handle this part of logic in above problem. I have been struggling to get this right with no idea. Suggestions provided will be appreciated. Culd you let me know what is the problem with the code/how to handle the additional constraint in this problem, :-((

Additional constraint says either u select as a group and not select as a group.so i dont know how to proceed.if u can PLEASE help me.it will be appreciated.

EDIT FOR USER->MISSINGNO: I have added the below code construct to above main code and it prints me wrong values.where have i gone wrong.

groupSumClump(0, {2, 4, 4, 8}, 14) → false is failing again 2 8 4 The flag is -->true which is wrong.

      for(int number=0;number<nums.length-1;number++){
      if(nums[number]==nums[number+1]){
          nums[number]=nums[number]+nums[number+1];                                
      }        
    }

I would convert the array to a simpler array that can be solved with your previous method, by clumping the adjacent values:

{1, 2, 2, 2, 5, 2} --> {1, 6, 5, 2}

You might want to keep some extra bookkeeping info though to be able to find the original solution from a solution to the altered problem.

This problem is similar to finding group of integers in an array which sum up to a given target.

Hint for this problem is:

The base case is when start>=nums.length. In that case, return true if target==0. Otherwise, consider the element at nums[start]. The key idea is that there are only 2 possibilities -- nums[start] is chosen or it is not. Make one recursive call to see if a solution is possible if nums[start] is chosen (subtract nums[start] from target in that call). Make another recursive call to see if a solution is possible if nums[start] is not chosen. Return true if either of the two recursive calls returns true.

You can use the same hint but with a loop in it to find sum of repeated numbers in array. Make a call to see if a solution is possible if the sum is chosen and make another call if the sum is not chosen.Return true if either of the two recursive calls returns true.

I think this would help.

public boolean groupSumClump(int start, int[] nums, int target)
{   
if(start >= nums.length) return target == 0;

int count = 1;
while(start+count < nums.length && nums[start] == nums[start+count])
count++;

if(groupSumClump(start+count, nums, target-count*nums[start])) return true;
if(groupSumClump(start+count, nums, target)) return true;

return false;
}

You Have taken quite a lengthy approach to solving this question. Try thinking more recursively.

For the Base Case, we'll check if the start is greater than or equal to the length of the provided array(nums). If it is true, we'll check if we've reached the target sum, i.e. target is equal to 0 or not. If it is, then we'll return true as we have an answer, else return false because we have traversed the whole array, and still not reached our target.

Base Case -

if(start>=nums.length)
return target==0;`

Now, we'll take a counter variable int c=1;. We'll use it to count the number of repeating characters present(if any). How we'll do it is, we will use a while loop and iterate till nums[start] to nums[start+c] and keep on increasing the counter by 1. When this loop will end, if the value of c is 1, then we didn't find any repeating characters. Else, we have found c repeating characters of nums[start]. Make Sure you don't go out of bounds in this while loop.

int c=1;
while(start+c<nums.length&&nums[start]==nums[start+c])
c++;

Now, you know if you have repeating characters or not. You either have to include all of them or none of them. We already have c, so now we just have to call the function in which it includes c*nums[start] or it doesn't include c*nums[start]

Now, if we have repetitions, the function will skip or take all of the same values. But if we don't have repetitions, just because the value of c is 1, the function call will work in this case too. Try to dry run the code to get a better idea.

In the end, if all the function calls return false, then we know that we don't have an answer, so we too will return false.

public boolean groupSumClump(int start, int[] nums, int target) {

if(start>=nums.length)
return target==0;

int c=1;

while(start+c<nums.length&&nums[start]==nums[start+c])
c++;

if(groupSumClump(start+c,nums,target- 
c*nums[start])||groupSumClump(start+c,nums,target))
return true;

return false;

}

Once you've done missingno's preprocessing step (in linear time) what you have is essentially the subset sum problem. It's a rather hard problem, but approximate algorithms exist- might as well turn out to be practical depending on how long your sequence is.

the problem statement is ambigious and not clear:

with this additional constraint: if there are numbers in the array that are adjacent and the identical value, they must either all be chosen, or none of them chosen. For example, with the array {1, 2, 2, 2, 5, 2}, either all three 2's in the middle must be chosen or not, all as a group

how about choosing single digits if the 'streaks' did not work out? same example: {1,2,2,2,5,2}

in one recursive call we choose the streak of 2 2 2 (from answer above) *if(groupSumClump(start+count, nums, target-count*nums[start])) return true*

in the next rec. call why can't we subtract the first single digit at nums[start]: if(groupSumClump(start+count, nums, target)) return true;

can i do this:

if(groupSumClump(start+1, nums, target - nums[start])) return true;

DOES IT MEAN WE CAN NEVER CHOOSE SINGLE DIGITS?

Your public method parameter list for the method groupSumClump should not expose the start parameter, especially if you have an internal variable that overrides it.

Have a look at this implementation. The time complexity for the solve method is O(2^N), since in the worst case you are obliged to check all possible subsets of nums. Well unless someone proves that NP = P.

I Hope it helps.

import java.util.*;

public class SubsetSumSolver {

    public boolean solve(int[] nums, int target) {
        return solve(0, 0, target, mergeSameNumbers(nums));
    }

    private boolean solve(int start, int tempSum, int sum, ArrayList<Integer> nums) {
        if (start == nums.size())
            return sum == tempSum;
        return solve(start + 1, tempSum + nums.get(start),sum, nums) || solve(start + 1, tempSum, sum, nums);
    }

    private ArrayList<Integer> mergeSameNumbers(int[] nums) {
        if (nums.length == 0)
            return toArrayList(nums);
        LinkedList<Integer> merged = new LinkedList<>();
        int tempSum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i - 1] == nums[i])
                tempSum += nums[i];
            else {
                merged.add(tempSum);
                tempSum = nums[i];
            }
        }
        merged.add(tempSum);
        return new ArrayList(merged);
    }

    private ArrayList<Integer> toArrayList(int[] nums) {
        ArrayList<Integer> result = new ArrayList();
        for (int index = 0; index < nums.length; index++)
            result.add(nums[index]);
        return result;
    }

}

My solution with a HasMap.

public boolean groupSumClump(int start, int[] nums, int target) {
  Map<Integer, Integer> map = new HashMap<Integer, Integer>();

  Arrays.sort(nums);

  for (int i : nums) {
    if (!map.containsKey(i)) {
      map.put(i, 1);
    }

    else {
      map.put(i, map.get(i) + 1);
    }
  }

  return groupSumClumpHelper(start, nums, target, map);
}

private boolean groupSumClumpHelper(int start, int[] nums, int target, Map map) {
  if (start >= nums.length) {
    return target == 0;
  }

  if (!map.get(nums[start]).equals(1)) {
    return groupSumClumpHelper(start + Integer.parseInt(map.get(nums[start]).toString()), nums, target - Integer.parseInt(map.get(nums[start]).toString()) * nums[start], map) ||
           groupSumClumpHelper(start + Integer.parseInt(map.get(nums[start]).toString()), nums, target, map);
  }

  return groupSumClumpHelper(start + 1, nums, target - nums[start], map) || groupSumClumpHelper(start + 1, nums, target, map);
}