Groupon Interview Question Interns
Country: India
Interview Type: Written Test
Hi,
In your algorithm, if the case is 6,3,1,7,9,6. Then if we keep track of RS in second pass, then after 7, RS=17 and then it just leaves without checking further elements. So, you might require little bit modification to maintain O(n) complexity.
Return false if total sum of the array is odd.
else, good luck.. This is NP-complete ("partition" problem) :)
exponential time algo should be straightforward.. Compute the power set.. Ignore the empty set and the "full" set, and consider every other set from the power set as a possible candidate..
Please refer to the following link for a dynamic programming approach to the problem
geeksforgeeks.org/dynamic-programming-set-18-partition-problem/
The link you provided solves the problem involving 'subsets' not 'subarrays' and takes >O(n) time.
However if only subarrays are involved then the problem can be solved without DP in O(n) time without using extra space.
public class ArrayPartition {
public static int [] integers = new int[]{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,10,6};
public static void main(String [] args){
int sum = findSumOfArray();
System.out.println(traverseArray(sum));
}
private static Boolean traverseArray(int sum){
Boolean reply = false;
int firstPart = 0;
int lastPart = 0;
for(int start = 0; start < integers.length; start++){
firstPart += integers[start];
lastPart = sum - firstPart;
if(firstPart == lastPart)reply = true;
}
return reply;
}
private static int findSumOfArray(){
int sum = 0;
for(int start = 0; start < integers.length; start++){
sum += integers[start];
}
return sum;
}
}
1>sort the array.
2>start from the largest element towards smallest
3>put the current element in the array which has lesser sum(if sum is equal,put on any side).
4>if it is possible to divide the array into two array with equal sum,it will get divided at the end of process else return -1.
please correct me if i am wrong
Have two pointers one starts from the left of the array and the other starts from the right of the array with the numbers added to their sum as they pass, lets say S1 and S2 are the sums. Move the left pointer to the right if S1 < S2, else move right pointer to left. Do this until they meet each other. When they meet each other if S1==S2 then we have got a solution, otherwise there is no solution.
public boolean hasPartition(int[] a) {
if(a == null || a.length < 2) return false;
int i = 0, j = a.length - 1;
int leftSum = 0, rightSum = 0;
while(i - 1 < j + 1) {
if (leftSum < rightSum) {
leftSum += a[i++];
}
else if (leftSum > rightSum) {
rightSum += a[j--];
}
else { // (leftSum == rightSum)
if(i > j) return true;
leftSum += a[i++];
rightSum += a[j--];
}
}
return false;
}
Please check if my approach is incorrect
public static boolean isPartitionable(int a[])
{
int sum=0;
for(int i=0;i<a.length;i++)
sum+=a[i];
if(sum%2!=0)
return false;
sum=sum/2;
int rs=0;
for(int i=0;i<a.length;i++)
{
int t=rs+a[i];
if(t==sum)
return true;
else if(t<sum)
rs=t;
}
return false;
}
private static void findSplit(int[] array) {
int startSum = array[0];
int endSum = array[array.length - 1];
int start = 0;
int end = array.length - 1;
while (start < end) {
if(start == (end -1)) {
break;
}
if (startSum == endSum) {
start++;
end--;
startSum += array[start];
endSum += array[end];
} else if (startSum > endSum) {
end--;
endSum += array[end];
} else {
start++;
startSum+= array[start];
}
}
if(startSum == endSum) {
System.out.println("There was a mid point at" + start );
} else {
System.out.println("There was no mid point");
}
}
private static void findSplit(int[] array) {
int startSum = array[0];
int endSum = array[array.length - 1];
int start = 0;
int end = array.length - 1;
while (start < end) {
if(start == (end -1)) {
break;
}
if (startSum == endSum) {
start++;
end--;
startSum += array[start];
endSum += array[end];
} else if (startSum > endSum) {
end--;
endSum += array[end];
} else {
start++;
startSum+= array[start];
}
}
if(startSum == endSum) {
System.out.println("There was a mid point at" + start );
} else {
System.out.println("There was no mid point");
}
}
public class EqualSumArraydetection {
/**
* @param args
*/
public static void main(String[] args) {
int[] arr= {5,1,5,11,10,5,7};
System.out.println(isqualSumarray(arr));
// TODO Auto-generated method stub
}
public static boolean isqualSumarray(int[] array){
for (int i=1; i<array.length; i++){
array[i]=array[i]+array[i-1];
}
for (int i=array.length-2; i>0; i--){
if (array[i]==array[array.length-1]-array[i]){
return true;
}
}
return false;
}
}
public class EqualSumArraydetection {
/**
* @param args
*/
public static void main(String[] args) {
int[] arr= {5,1,5,11,10,5,7};
System.out.println(isqualSumarray(arr));
// TODO Auto-generated method stub
}
public static boolean isqualSumarray(int[] array){
for (int i=1; i<array.length; i++){
array[i]=array[i]+array[i-1];
}
for (int i=array.length-2; i>0; i--){
if (array[i]==array[array.length-1]-array[i]){
return true;
}
}
return false;
}
}
#include<iostream>
#include<stdio.h>
using namespace std;
int main(void)
{
int a[]={1 ,1 ,2 ,2, 1, 1} ;
int size=sizeof(a)/sizeof(a[0]);
int j=size-1; //from end
int i=0; //from start
int suml=0,sumr=0;
while(i<=j)
{
if(suml<=sumr)
{
suml=suml+a[i];
i++;
}
else
{
sumr=sumr+a[j];
j--;
}
}
if(sumr==suml)
cout<<"TRUE";
else
cout<<"FALSE";
return 0;
}
#include<iostream>
#include<stdio.h>
using namespace std;
int main(void)
{
int a[]={1 ,1 ,2 ,2, 1, 1} ;
int size=sizeof(a)/sizeof(a[0]);
int j=size-1; //from end
int i=0; //from start
int suml=0,sumr=0;
while(i<=j)
{
if(suml<=sumr)
{
suml=suml+a[i];
i++;
}
else
{
sumr=sumr+a[j];
j--;
}
}
if(sumr==suml)
cout<<"TRUE";
else
cout<<"FALSE";
return 0;
}
If this question is only concern with the sequentially formed elements it is an O(n) problem:
int i,j,sum=0,s=0,flag=0;
for(i=0;i<n;i++)
sum+=a[i];
if(sum%2!=0)
{
printf("\nIt cannot be broken into two subarray of equal sums\n");
return;
}
for(i=0;i<n;i++)
{
s+=a[i];
if(sum-s==0)
{
flag=i;
break;
}
sum-=s;
}
if(flag!=0)
{
for(j=0;j<flag;j++)
printf("%d\t",a[j]);
for(j=flag;j<n;j++)
printf("%d\n",a[j]);
}
else
printf("\n It cannot be broken into two subarray of equal sums\n");
However, its complexity grows exponentially, as pointed out by others, with the size of the input.
1. First pass, find the sum S of all the numbers in the array
- oOZz August 13, 20132. Second pass, keep a running sum RS and check if RS == (S - RS), return true
3. Return false at the end