Apple Interview Question
This is all well and good, but you still need to check for an end condition, that is if the index "start" exceeds the array's length. Do this after the first condition check in the helper method.
<pre lang="" line="1" title="CodeMonkey48804" class="run-this">/* The class name doesn't have to be Main, as long as the class is not public. */
class Main
{
public boolean checkSum(int[] arr, int st, int end, int sum){
if(sum==0)return true;
for(int i=st;i<end;i++){
int tmp = sum - arr[i];
if(tmp <0)continue;
if(checkSum(arr, i+1, end, tmp))return true;
}
return false;
}
public boolean splitArray(int[] arr){
int sum = 0;
for(int i=0;i<arr.length();i++)sum+=arr[i];
return checkSum(arr, 0, arr.length(), sum/2);
}
public static void main (String[] args) throws java.lang.Exception
{
int[] arr = {2,3,5,6,2};
if(splitArray(arr))System.out.println("true");
else System.out.println("false");
return;
}
}
</pre><pre title="CodeMonkey48804" input="yes">
</pre>
I think this will work, hope to see some better solution
package ArraysAndStrings;
import java.util.Arrays;
public class ArraySepValue {
public boolean canDivide(int[] input) {
if(input.length < 2)
return false;
double sum = 0;
for(int x : input)
sum += x;
Arrays.sort(input);
if(sum % 2 == 1)
return false;
return canDivHandler(input, 0, sum / 2);
}
public boolean canDivHandler(int[] input, int start, double sum) {
if(start == input.length || input[start] > sum)
return false;
int cur = input[start];
if(cur == sum)
return true;
start += 1;
return canDivHandler(input, start, sum) || canDivHandler(input, start, sum - cur);
}
public static void main(String[] args) {
int[] array = new int[]{3,3,3,3,3,7,1};
ArraySepValue a = new ArraySepValue();
System.out.println(a.canDivide(array));
}
}
//using dynamic programming
bool splitArray(int[] array){
int sum = sum(array);
int i = count(array);
return Q(array, i, sum/2);
}
Q(int[] array, int i, int sum){
if(i == 1){
return array[i]==sum?true:false;
}
if((array[i]==sum)
|| Q(array, i-1, sum-array[i]) //have a subset with array[i]
|| Q(array.removeAt(i), i-1, sum)) //have a subset without array[i]
return true;
else
return false;
}
Here is my solution in C
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
int sum(int array[], int start, int end){
int sum = 0, i;
for(i = start; i < end; i++){
sum += array[i];
}
return sum;
}
int splitArray(int array[], int start, int end, int ind){
if( ind == end){
return 0;
} else {
int left = sum(array, start, ind);
int right = sum(array, ind+1, end);
return (left == right) || splitArray(array, start, end, ind+1);
}
}
int main(int argc, char* argv[]){
int array[] = { 7,3,4,0,1,2};
int res = splitArray(array, 0, 5, 0);
if( res == 1)
printf("TRUE\n");
else
printf("FALSE\n");
return 0;
}
Here is my solution in C
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
int sum(int array[], int start, int end){
int sum = 0, i;
for(i = start; i < end; i++){
sum += array[i];
}
return sum;
}
int splitArray(int array[], int start, int end, int ind){
if( ind == end){
return 0;
} else {
int left = sum(array, start, ind);
int right = sum(array, ind+1, end);
return (left == right) || splitArray(array, start, end, ind+1);
}
}
int main(int argc, char* argv[]){
int array[] = { 7,3,4,0,1,2};
int res = splitArray(array, 0, 5, 0);
if( res == 1)
printf("TRUE\n");
else
printf("FALSE\n");
return 0;
}
#include "stdio.h"
2
3 int splitArray(int list[], int index)
4 {
5 int i, sum1, sum2;
6 /* left half */
7 sum1 = 0;
8 for(i=0;i<index;i++)
9 sum1 = sum1 + list[i];
10 /* right half */
11 sum2 = 0;
12 for(i=index;i<6;i++)
13 sum2 = sum2 + list[i];
14
15 if(sum1 == sum2)
16 return 1;
17 else
18 return 0;
19 }
20
21
22 int main(void)
23 {
24 int i, list[] = { 7,0, 2, 3,4,2};
25
26 for(i=0;i<6;i++)
27 if(splitArray(list, i)) {
28 printf(" TRUE \n");
29 break;
30 }
31 }
~
#if 1
#include <stdio.h>
#include <stdlib.h>
int sum(int array[], int start, int end)
{
int sum = 0, i;
for(i = start; i < end; i++)
{
sum += array[i];
}
return sum;
}
int splitArray(int array[], int start, int end, int ind)
{
if( ind == end)
{
return 0;
}
else
{
int left = sum(array, start, end);
printf("\n total sum of all elements in array \n");
//int end1 = (end)/2;
ind = ind+1;
int left1 = sum(array,start,ind);
int right = sum(array, ind, end);
if(left1 == right)
return 1;
else
splitArray(array, start, end, ind);
}
}
int main(int argc, char* argv[])
{
int array1[] = {5,2,2,4,5};
int len = sizeof(array1)/ sizeof(array1[0]);
int res = splitArray(array1, 0, len, 0);
if( res == 1)
printf("TRUE\n");
else
printf("FALSE\n");
return 0;
}
long sum(array a)
{
result = 0;
for all element x in a
result += x;
return result;
}
BOOL recursiveSplit(index, previousSum, targetSum, array a)
{
currentSum = 0;
if(index < 0) return no;
if(a[index] == targetSum || (a[index] + previousSum) == targetSum) return yes;
if(a[index] + previousSum > targetSum)
currentSum = previousSum;
else
currentSum = previousSum + a[index];
return recursiveSplit(index - 1, currentSum, targetSum, a);
}
main()
{
array a = [1,1,1,1,4,2];
index = a.length - 1;
targetSum = sum(a)/2;
if(recursiveSplit(index, 0, targetSum, a))
log("YES");
else
log("NO");
}
only loop is for initial sum of the array...
#include <iostream>
using namespace std;
bool test(int x[], int i, int sum, int cursum, int n, bool take)
{
bool done=false;
if (take)
cursum += x[i];
i++;
if (cursum<sum && i<n)
done = test(x,i,sum,cursum,n,true) || test(x,i,sum,cursum,n,false);
else if(cursum==sum)
done = true;
return done;
}
bool splitArray(int x[], int n)
{
int sum=0;
for (int i=0; i<n; i++)
sum+=x[i];
int halfsum = sum/2;
if (halfsum*2 != sum)
return false; //sum needs to be even
return test(x,0,sum/2,0,n,true) || test(x,0,sum/2,0,n,false);
}
int main (int argc, char * const argv[]) {
int x[]={2,3,20,5,10};
int len = sizeof(x)/ sizeof(x[0]);
cout << (splitArray(x,len)?"true":"false");
cout << "\n";
return 0;
}
Here is a solution in C (it actually computes the sum as it checks if the partition is possible).
We need to rely on the array being sorted beforehand for this.
#include <stdlib.h>
#include <stdio.h>
int compare_function(const void *a,const void *b) {
int *x = (int *) a;
int *y = (int *) b;
return *x - *y;
}
int array_partition_possible(int *array, int count) { //array needs to be already sorted
int sum_a = 0;
int sum_b = 0;
for (int i = count-1; i >= 0; i--) {
if (sum_a <= sum_b) {
sum_a += array[i];
} else {
sum_b += array[i];
}
}
printf("%d, %d\n",sum_a, sum_b );
return (sum_a == sum_b);
}
int main(int argc, char *argv[]) {
int count = argc - 1;
// Create the input array based on the arguments of the main function.
int *input = malloc(count);
for (int i = 0; i < count; ++i) {
input[i] = atoi(argv[i+1]);
}
// Sort the input array
qsort(input, count, sizeof(*input), compare_function);
// Find if the partition is possible
if (array_partition_possible(input, count))
{
printf("true\n");
} else {
printf("false\n");
}
return 0;
}
This solution can also be found here: h**ps://gist.github.com/nilsou/6969993
#include <iostream>
using namespace std;
bool isPartition(int* arr, int n) {
int sum = 0;
for (int i = 0; i < n; i++) {
sum = sum + arr[i];
}
if (sum & 1) {
return false;
}
sum = sum / 2;
bool** T = new bool*[n + 1];
for (int i = 0; i < n + 1; i++) {
T[i] = new bool[sum + 1];
}
// Initializing the first row as false
for (int j = 0; j < sum + 1; j++) {
T[0][j] = false;
}
// Initializing the first column as true
for (int i = 0; i < n + 1; i++) {
T[i][0] = true;
}
// Computing the T matrix
for (int i = 1; i < n + 1; i++) {
for (int j = 1; j < sum + 1; j++) {
if (j < arr[i - 1]) {
T[i][j] = T[i - 1][j];
}
else {
T[i][j] = T[i - 1][j] || T[i - 1][j - arr[i - 1]];
}
}
}
return T[n][sum];
}
int main() {
int arr[] = { 3, 1, 1, 2, 2, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << isPartition(arr, n) << endl;
}
#include <iostream>
using namespace std;
bool splitarrayex(int *array, int numele, int sum1, int sum2)
{
if (sum1 == sum2 && numele == 0)
return true;
if (numele == 0)
return false;
return splitarrayex(array+1, numele-1, sum1+(*array), sum2) || splitarrayex(array+1, numele-1, sum1, sum2+(*array));
}
int main()
{
// int array [] = {1, 2, 5, 6};
int array [] = {5, 2, 3, 4, 2};
// int array [] = {5, 2, 3, 4, 30};
if (splitarrayex(array, 5, 0, 0))
cout << "TRUE" << endl;
else
cout << "FALSE" << endl;
return 0;
}
#include <iostream>
using namespace std;
bool splitarrayex(int *array, int numele, int sum1, int sum2)
{
if (sum1 == sum2 && numele == 0)
return true;
if (numele == 0)
return false;
return splitarrayex(array+1, numele-1, sum1+(*array), sum2) || splitarrayex(array+1, numele-1, sum1, sum2+(*array));
}
int main()
{
// int array [] = {1, 2, 5, 6};
int array [] = {5, 2, 3, 4, 2};
// int array [] = {5, 2, 3, 4, 30};
if (splitarrayex(array, 5, 0, 0))
cout << "TRUE" << endl;
else
cout << "FALSE" << endl;
return 0;
}
partitioning question...can be done using dynamic programming
let P(i,b) be true if there is a subset of array from a1 to ai such that its sum is b
P(i,b) = max (P(i-1,b), P(i-1, b-a[i]))
- Nitin Bhatt September 11, 2011#include <iostream> using namespace std; bool splitarrayex(int * array, int start, int sum) { if (sum == 0) {return true;} if (array[start] == sum){return true;} if (array[start] > sum ){ start++; return splitarrayex(array, start, sum);} else{ sum = sum - array[start]; start++; return splitarrayex(array, start, sum); } } int main() { int array [] = {1, 2, 5, 6}; int sum = 0; for (int i = 0 ; i < 4 ;i ++) { sum += array[i]; } int half = sum/2; if (sum == half * 2) { if (splitarrayex(array, 0 , sum/2)){printf("\r\n TRUE \r\n");} else{printf("\r\n FALSE \r\n");} } else { printf("\r\n FALSE \r\n"); } return 0; }