TP Interview Question
SDE1sCountry: United States
Interview Type: Phone Interview
Ditto what alex said.
This check is unnecessary: if(sum < arr[n-1])
return IsSumForOdd(arr, n-1, count, sum);
An additional check that is needed is if (n == 0) { return false; }
I think the following will work
int IsSumForOdd(int* a,int n,int counter,int sum)
{
if(a[n] == 0)
return 1;
if(sum == 0)
if (counter%2 == 0)
return 1;
else
return 0;
if(sum<0)
return 0;
if(n==0)
return 0;
if(sum<a[n-1])
return doSearch(a,n-1,counter,sum);
return doSearch(a,n-1,counter+1,sum-a[n-1])||doSearch(a,n-1,counter,sum);
}
Modified subset sum problem and it works here as well.
int total=0;
#define SIZE(a) sizeof(a)/sizeof(a[0])
int arr[] = {2, 11, 20, 30, 31};
int counter = 0;
void IsSubArray(int n, int N, int sum) // N is the number of elements in the array
{
counter++;
if(sum == N) {
if(((counter%2) == 1)) {
printf("got it\n");
counter--;
}
return;
}
if((n <= (SIZE(arr)-1)) && arr[n]+sum <= N) {
IsSubArray(n+1, N, sum+arr[n]);
}
if((n <= (SIZE(arr)-1)) && arr[n+1]+sum <= N) {
counter--;
IsSubArray(n+1, N, sum);
}
}
int main()
{
int j, i;
int target_sum=51;
IsSubArray(0, target_sum, 0);
return 0;
}
bool HasOddSum(int arr[], int len, int count, int sum)
{
if ((sum == 0) && (count % 2 == 1))
return true;
else if (sum < 0 || len < 0)
return false;
else if (sum < arr[len - 1])
return HasOddSum(arr, len - 1, count, sum);
else
return HasOddSum(arr, len - 1, count + 1, sum - arr[len - 1]) || HasOddSum(arr, len - 1, count, sum);
}
void RunDriver()
{
//input
int arr[] = {3, 23, 44, 2, 11};
int sum = 16;
cout << endl << "Array " << (HasOddSum(arr, sizeof(arr) / sizeof(arr[0]), 0, sum) ? "has" : "has't") << " sum " << sum << " with odd number of elements" << endl;
}
You are right... my code doesn't work for 0... but it can be modified slightly to resolve that problem as well.. :)
function checkExists(arr,length,count,k)
{
if(k==0 && count%2==1)
return true;
else if(k<0 || length<0)
return false;
else if(k<arr[length-1])
return checkExists(arr,length-1,count,k);
else
return checkExists(arr,length-1,count+1,k-arr[length-1]) || checkExists(arr,length-1,count,k);
}
explanation:
1. check if sum=0 and count is odd [one end case of recursion]
2. check if sum<0 or length<0 [recursion lands into out of boundary cases]
3. check if the sum to be found is lesser than last element of array considered as it is sorted if yes ....dont consider last element and recurse.
4. if the sum is greater than the last element, it[last element] can or cannot be a part of the numbers which are involved in the odd sum. so consider once in recursion "or" dont consider
Please let me know if something is wrong here
- DashDash May 10, 2013bool IsSumForOdd(int *arr, int n, int count, int sum)
{
if(sum == 0 && count%2 == 0)
return true;
if(sum < 0)
return false;
if(sum < arr[n-1])
return IsSumForOdd(arr, n-1, count, sum);
else
{
return (IsSumForOdd(arr, n-1, count+1, sum-arr[n-1])) || (IsSumForOdd(arr, n-1, count, sum));
}
}