Geek asks and answers

Java Algorithm Question

Problem Statement :: In Java. Given an array of ints, you can select a group of some of ints, so the group is summed up for a given purpose with this additional limitation: if they must be selected or not selected in an array that is adjacent and identical in value. For example, with the array {1, 2, 2, 2, 5, 2}, or all three 2 in the middle should be selected or not, all as a group. (one cycle can be used to determine the degree of 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 did the initial analysis, and the partial code is below.

  public 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;
}

: , : Additional Constraint , , , , , . , {1, 2, 2, 2, 5, 2}, 2 , . ( ).

. , . . Culd, , / : - ((

, , group.so , . , . .

→ MISSINGNO: , . .

groupSumClump (0, {2, 4, 4, 8}, 14) → false 2 8 4 → true, .

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

, , :

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

, , .

+6

, .

:

- start >= nums.length. true, target == 0. nums [start]. , : nums [start] . , , , nums [start] ( nums [start] ). , , , nums [start] . true, true.

, , . , , , , . true, true.

, .

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;
}
+3

, missingno ( ), , , . , , , .

0

:

: , , . , {1, 2, 2, 2, 5, 2}, 2 ,

, "" ? : {1,2,2,2,5,2}

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

rec. , nums [start]: if (groupSumClump (start + count, nums, target)) true;

:

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

, ?

0

groupSumClump start, , .

. solve O(2^N), nums. , - , NP = P.

, .

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;
    }

}
0

More articles:


All Articles