## Athena Health Interview Question

Software Engineer / Developers**Country:**India

**Interview Type:**In-Person

I allowed myself to write the implementation using DP approach:

```
public static void main(String[] args) {
// int[] arr = { 5, 7, 3, 3 };
int[] arr = { 3, 2, 1 };
// int[] arr = { 1, 5, 11, 5 };
int sum = 0;
for (int i = 0; i < arr.length; i++) {
sum += arr[i];
}
System.out.println("Sum: " + sum);
boolean[][] sums = new boolean[arr.length][sum + 1];
for (int i = 0; i < sums.length; i++) {
sums[i][0] = true;
}
sums[0][arr[0]] = true;
for (int i = 1; i < sums.length; i++) {
for (int j = 0; j < sums[0].length; j++) {
if (sums[i - 1][j] == true) {
sums[i][j] = true;
sums[i][j + arr[i]] = true;
}
}
}
// printMatrix(sums);
int half = sum / 2;
while (!sums[sums.length - 1][half]) {
half--;
}
System.out.println("Closest to half of the sum: " + half);
Set<Integer> firstHalfIndexes = new HashSet<Integer>();
int rowWithHalf = sums.length - 1;
while (half > 0) {
while (rowWithHalf >= 0 && sums[rowWithHalf][half]) {
rowWithHalf--;
}
rowWithHalf++;
firstHalfIndexes.add(rowWithHalf);
half -= arr[rowWithHalf];
}
List<Integer> firstHalf = new ArrayList<Integer>(firstHalfIndexes.size());
List<Integer> secHalf = new ArrayList<Integer>(arr.length - firstHalfIndexes.size());
for (int i = 0; i < arr.length; i++) {
if (firstHalfIndexes.contains(i)) {
firstHalf.add(arr[i]);
} else {
secHalf.add(arr[i]);
}
}
System.out.println("First team: " + firstHalf);
System.out.println("Sec team: " + secHalf);
System.out.println("Diff: " + Math.abs(firstHalf.size() - secHalf.size()));
}
```

Can you please explain your code a bit? In particular, I'm having a lot of difficulty following what you are doing here:

[code]

Set<Integer> firstHalfIndexes = new HashSet<Integer>();

int rowWithHalf = sums.length - 1;

while (half > 0) {

while (rowWithHalf >= 0 && sums[rowWithHalf][half]) {

rowWithHalf--;

}

rowWithHalf++;

firstHalfIndexes.add(rowWithHalf);

half -= arr[rowWithHalf];

}

[/code]

Many thanks in advance!

{

General Approach:-

Sort the elements into descending order.

Divide the array into 1 and n-1 sub arrays

Find the sum difference if it is equal you got the solution otherwise move the smallest element from set 2 to set one and keep on checking until you got the sum equal.

}

Here is some code about the problem.

int splitPlayers(int[] set) {

int n = set.length;

int sum = 0;

for(int s:set) {

sum += s;

}

sum /= 2;

boolean[][] subset = new boolean[sum+1][n];

int[][] count = new int[sum+1][n];

subset[set[0]][0] = true;

count[set[0]][0] = 1;

for (int i = 1; i <= sum; i++) {

for (int j = 0; j < n; j++) {

if (set[j] == i) {

subset[i][j] = true;

count[i][j] = 1;

} else if (j > 0) {

if (i >= set[j]) {

subset[i][j] = subset[i][j-1] || subset[i - set[j]][j-1];

if (subset[i - set[j]][j-1] == true) {

count[i][j]=count[i - set[j]][j-1]+1;

} else if(subset[i][j-1]==true) {

count[i][j] = count[i][j-1];

}

}

else {

subset[i][j] = subset[i][j-1];

}

}

}

}

if(!subset[sum][n-1]){

return 0;

}

int min = Integer.MAX_VALUE;

for (int i = 0; i < n; i++) {

if (count[sum][i] != 0) {

int onepart = n - count[sum][i];

int other = n - onepart;

min = Math.min(min, Math.abs(onepart-other));

}

}

return min;

}

I implemented in dp but i couldnt find bug in my code can anybody help.Logic for every value from last i check whether to put in which optimal team.

#include<stdio.h>

int findMin(int a,int b){

if(a<b)

return a;

else

return b;

}

int findDifference(int arr[3],int n,int firstsum,int secondsum,int firstcount,int secondcount){

if(n<0){

if(firstsum == secondsum){

printf("%d\n",firstsum );

return firstcount -secondcount;

}

}

else

findMin(findDifference(arr,n-1,firstsum+arr[n],secondsum,firstcount++,secondcount),

findDifference(arr,n-1,firstsum,arr[n]+secondsum,firstcount,secondcount++));

}

int main()

{

int arr[]={3,1,6,3,1};

int size=3;

printf("%d\n",findDifference(arr,3,0,0,0,0) );

}

#include<stdio.h>

int findMin(int a,int b){

if(a<b)

return a;

else

return b;

}

int findDifference(int arr[3],int n,int firstsum,int secondsum,int firstcount,int secondcount){

if(n<0){

if(firstsum == secondsum){

printf("%d\n",firstsum );

return firstcount -secondcount;

}

}

else

findMin(findDifference(arr,n-1,firstsum+arr[n],secondsum,firstcount++,secondcount),

findDifference(arr,n-1,firstsum,arr[n]+secondsum,firstcount,secondcount++));

}

int main()

{

int arr[]={3,1,6,3,1};

int size=3;

printf("%d\n",findDifference(arr,3,0,0,0,0) );

}

This is a variation of well-known NP-problem (en.wikipedia.org/wiki/Partition_problem). So the only solution is backtracking.

- JacVlD January 31, 2013