Amdocs Interview Question
Country: United States
vgeek
Can you please explain why S1=S/2 (in your logic: S=S1+S2 or S=2S1 so S1=S/2) .
S1 and S2 are not same values so you wont be able to make S1 as S/2.
Consider the example given in the question (11+4 = 2+5+1+7)
Here if S1 = 11 then S2 does not come out to be same as S1. S2 is 19 (4+ 2+5+1+7)
Also in your second logic of self balancing AVL tree, how can you just remove a duplicate element
Consider an array {1,1,4,1,1,1,1} So here S1 is 4 and S2 is 1. In your AVL tree logic, if you ignore duplicate elements then your avl tree will only have 1 as root and 4 as the right child.
Now any logic of S1-arr[i] will never find element there because possible answers for S1 being 1,1,4,1,1,1 and arr[i] being remaining elements will either be 3 (4-1) or -3 (1-4) or 0 (1-1). None of these values are in the AVL tree.
If I have mis understood the logic, please explain.
No first find out the sum of the whole array S which turns out to be 30. So now S1 and S2 become 15. So now the problem reduces to finding a pair in the array whose sum is 15. S1 and S2 are just the notations used for sum of two elements (S1) and sum of rest of the elements (S2). Regarding duplicates they are not removed from the array, they are just not considered as we have to find 2 elements whose sum is equal to the rest of the elements of the array.
I think I can find an algorithm in O(n) time.
If the array can be separate into two parts, which is S1 = S2, and S1 = a + b, and S2 = summation of the rest element. We can process the array in this way:
First, get the sum of the array, in the example, sum{2,11,5,1,4,7} = 30. Then we can let it divided by 2, so it becomes 30/2 = 15.
Second, this problem becomes that whether we can find two elements in the array, and the summation is 15. So we need a hashmap to store all the subtraction of 15 and elements in the array. The key will be the subtraction and the value will be the element's index. So in this example, the hashmap will have the key-value pairs like this: {(4, 1),(8, 5),(10, 2),(11, 4),(13, 0),(14, 3)}. You can see that there is one pair: (13, 0), it means that the 0th element in the array, which is 2, 2+13 = 15. So, the 1st element in the array is 11 and 4+11 = 15.
Third, after we have the hashmap, we can traverse the array from left to right. When we meet the element in the array, we check if we can find the same number in the hashmap by key value. For example, we the first element in the arrray is 2, and we cannot find this key value in the hashmap. Then we 11, and we can find 11 in the hashmap and the value is 4, it means that in the array 11 puls the 4th element in the array equals to 15. The 4th element in the array is 4, which is correct. So if we can find the array and the hashmap share the same number, it means we can find 2 elements in the array with the sum equals to the sum of the rest elements in the array.
In the algorithm, get sum and divide it by 2 requires O(n) time, create the hashmap needs O(n) time, and traverse the array still needs O(n) time. The total complexity will be O(n).
#include <iostream>
#include <map>
using std::cin;
using std::endl;
using std::cout;
using std::map;
class demo
{
private:
int *arr;
int length;
public:
demo(int a[], int n)
{
arr = new int[n];
length = n;
for(int i=0; i<n; i++)
{
arr[i] = a[i];
}
}
~demo()
{
delete [] arr;
cout<<"Array deleted..."<<endl;
}
bool twoSum()
{
int sum = 0;
map<int, int> sub;
bool result = false;
for(int i=0; i<length; i++)
{
sum = sum + arr[i];
}
sum = sum/2;
for(int i=0; i<length; i++)
{
sub[(sum-arr[i])] = i;
}
for(int i=0; i<length; i++)
{
if(sub.find(arr[i]) != sub.end())
{
result = true;
return result;
}
else
{
result = false;
}
}
}
};
int main(int argc, const char * argv[])
{
// insert code here...
int a[] = {2, 11, 5, 1, 4, 7};
demo d(a, 6);
if(d.twoSum()){
cout<<"The result is true..."<<endl;
}
else{
cout<<"The result is false..."<<endl;
}
system("pause");
return 0;
}
Oh, I forgot to mention that in the second step, 2+13 = 15, how ever, there is not 13 in the array, so we will not query this pair. Which means that when we see 2 in the array, we cannot find any pair in the hashmap. So we can only find 4 and 11 pair in the hashmap.
I think the above 2 algorithms are great. As an additional performance improvement, if we find the sum is odd, we can directly return false since if the sum of all elements is odd, it is impossible to have 2 numbers in the array whose sum is equal to the sum of the rest of the numbers in the array.
//Check there exists a pair whose sum is equal to rest of elements of array
//Duplicate elements can be there
#include<iostream>
using namespace std;
void swap(int &i, int &j)
{
int temp = i;
i = j;
j = temp;
}
int partition(int arr[], int low, int high)
{
int i = low;
int j = high;
j--;
int p = arr[high];
while(i < j)
{
if(arr[i] <= p)
{
i++;
}
else if(arr[j] > p)
{
j--;
}
else
{
swap(arr[i],arr[j]);
i++;
j--;
}
}
if(arr[i] == p)
{
return i;
}
else if(arr[i] > p)
{
swap(arr[i],arr[high]);
return i;
}
else
{
swap(arr[i+1],arr[high]);
return i+1;
}
}
void q_sort(int arr[], int low, int high)
{
if(low < high)
{
int p = partition(arr,low,high);
q_sort(arr,low,p-1);
q_sort(arr,p+1,high);
}
}
//This will return true if there exists a pair whose sum is equal to
//sum of all other elements
bool isExistsPair(int arr[], int n)
{
int sum = 0;
for(int i = 0; i < n; i++)
{
sum+=arr[i];
}
if(sum%2 != 0) return false;
q_sort(arr,0,n-1);
int k = sum/2;
int i = 0;
int j = n-1;
while(i < j)
{
if(arr[i] + arr[j] == k)
{
cout<<arr[i]<<" "<<arr[j]<<endl;
return true;
}
else if(arr[i] + arr[j] < k)
{
i++;
}
else
{
j--;
}
}
return false;
}
int main()
{
int arr[] = {1,8,3,20,4,4,2};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<isExistsPair(arr,n);
return 0;
}
public class P1 {
public int sum(int[] array) {
int sum = 0;
for (int i : array) {
sum += i;
}
return sum;
}
public boolean check(int sum, int[] array) {
boolean check = false;
for (int i = 0; i < array.length; i++) {
for (int j = i+1; j < array.length;j++) {
int count = array[i] + array[j];
int remaining = sum - count;
System.out.println("count--->" + count + " remaining--->"
+ remaining);
if (count == remaining) {
check = true;
break;
}
}
}
return check;
}
public static void main(String[] args) {
int[] array = { 2, 11, 5, 1, 4, 7 };
P1 p = new P1();
int total = p.sum(array);
boolean check = p.check(total, array);
System.out.println("The condition for the array is---->" + check);
}
}
import java.util.Arrays;
public class SumOfTwo {
public static int maxp = 5;
public static int minp = 0;
public static int temp = 0;
public static int half = 15;
public static void main(String[] args) {
int[] given = { 2, 11, 5, 1, 4, 7 };
Arrays.sort(given);
System.out.println(check(given));
}
public static boolean check(int[] array) {
if (maxp >= 0 && minp <= 5) {
temp = array[minp] + array[maxp];
if (temp < half) {
minp = minp + 1;
return check(array);
} else if (temp > half) {
maxp = maxp - 1;
return check(array);
} else
return true;
} else
return false;
}
}
public static boolean searchSum(int[] A) {
int sum = 0;
int halfsum = 0;
if (A.length <=2) {
return false;
}
else{
for(int i : A) {
sum += i;
}
if (sum % 2 != 0) return false;
else{
boolean res = false;
Arrays.sort(A);
halfsum = sum/2;
for (int j = 0; j < A.length-1; j++) {
int diff = halfsum - A[j];
int ret = Arrays.binarySearch(A, j+1, A.length, diff);
return (ret != -1);
}
return res;
}
}
}
solution without using hash tables with time complexity o(n)
Here we need to find two elements whose sum is equal to half of total sum.
solution:
initially i would check whether the sum of total elements in array is even or not,then i would check whether the sum of first and second largest elements is greater than half of total sum or not.If these cases are satisfied(total sum -even and second case),i will check for elements which are equal or greater than 1/4 of total sum and less than 1/2 of total sum.After finding these elements(i may get at a maximum of 4 elements of these kind),i will check for elements corresponding to these elements whose sum is equal to 1/2 of total sum
You may miss the case of {3,3,0,6} or {1,3,4,6}... if you check the second and largest element. Imaging those given arrays like negative and positive skewed distribution.
import java.util.Arrays;
public class ElementFinder {
public static void main(String[] args) {
int [] arr = new int[] {2,11,5,1,4,7};
int sum = 0;
for(int num : arr){
sum = sum + num;
}
boolean isPairExist = false;
Arrays.sort(arr);
for(int i=0;i<arr.length;i++){
int firstNum= arr[i];
int secondNumber = sum/2 - firstNum;
int index = binarySearch(arr,secondNumber,0,arr.length-1);
if(index !=-1){
isPairExist = true;
break;
}
}
System.out.println(isPairExist);
}
public static int binarySearch(int[] arr,int value,int left,int right){
if(left > right)
return -1;
int mid = (left+right)/2;
if(arr[mid] == value)
return mid;
else if(arr[mid] > value)
return binarySearch(arr,value,left,mid-1);
else
return binarySearch(arr,value,mid+1,right);
}
}
here goes mine in objective O(n) times i think
NSMutableArray *numbers = [NSMutableArray arrayWithObjects:@2, @11, @5, @1, @4, @7, nil];
if ([numbers count] < 3) {
NSLog(@"not enough elements");
return 0;
}
__block long sum = 0;
[numbers enumerateObjectsUsingBlock:^(NSNumber *obj, NSUInteger idx, BOOL *stop) {
sum += [obj doubleValue];
}];
if (sum %2 != 0) {
NSLog(@"cant find a sum for decimal numbers");
return 0;
}
NSSortDescriptor *sort = [NSSortDescriptor sortDescriptorWithKey:nil ascending:NO];
numbers = [[numbers sortedArrayUsingDescriptors:@[sort]] mutableCopy];
double total = sum/2;
for (int i = 0; i < numbers.count/2; i++) {
long temporal = [numbers[i] doubleValue];
for (int j = i + 1; j < numbers.count; j++) {
long maxSum = [numbers[j] doubleValue];
if ((maxSum + temporal) < total) {
NSLog(@"nothing here");
break;
} else if ((maxSum + temporal) == total) {
NSLog(@"we have a match. condition foudned sum numbers are %ld, %ld, against the rest", temporal, maxSum);
return 0;
}
}
}
Why not use a simple array..following is pseudocode..
1. Sort array A[0..length-1] and get sum of all elements as totalSum.
2. Set start counter to 0 and end counter at lenght - 1.
3. Get sum currentSum = A[start] + A[end].
4. Get sum restElementSum = totalSum - currentSum.
5. If restElementSum == currentSum then print A[start] and A[end] return
6. Else start-- and end--
7. Goto 3.
vgeeks's 3rd algorithm in java:
boolean twoSum(int[] input) {
int sum = getSum(input);
if (sum % 2 == 1) {
return false;
}
int target = sum / 2;
Set<Integer> seen = new HashSet<Integer>();
for (int i = 0; i < input.length; ++i) {
if (seen.contains(target - input[i])) {
return true;
}
seen.add(input[i]);
}
return false;
}
int getSum(int[] input) {
int sum = 0;
for (int i = 0; i < input.length; ++i) {
sum += input[i];
}
return sum;
}
akkaiah.j's solution (assuming non-negative integers):
(I'm not checking if the two largest integers are greater or equal to the target sum as it isn't necessary and doesn't improve the asymptotic run time)
boolean nonNegativeTwoSum(int[] input) {
sum = getSum(input);
if (sum % 2 == 1) {
return false;
}
int target = sum / 2;
int[] candidates = new int[4];
int candidatesFound = 0;
int halfTarget = (target + 1) / 2; // Adding 1 to target in case it is odd. I want it to round up. Needed to guarantee at most 4 candidates (if we round down, [1,1,1,1,1,1] will give us 6 candidates...).
for (int i = 0; i < input.length; ++i) {
if (input[i] >= halfTarget) {
candidates[candidatesFound++] = i;
}
}
for (int i = 0; i < input.length; ++i) {
for (int j = 0; j < candidatesFound; ++j) {
if (input[i] + input[candidates[j]] == target && i != candidates[j]) {
return true;
}
}
}
return false;
}
public class Test{
public static void main(String args[]){
int a[]={2,11,5,1,4,7};
System.out.println("Integer Array Initialy:-"+Arrays.toString(a));
int temp,sum=0;
for(int i=0; i<a.length;i++){
for (int j=i+1;j<a.length;j++){
if(a[i]>a[j]){
temp=a[j];
a[j]=a[i];
a[i]=temp;
}
}
}
int len=a.length;
for(int i=0;i<len;i++)
sum+=a[i];
sum/=2;
System.out.println("Integer Array after Sorting:-"+Arrays.toString(a));
temp=0;
for(int i=0;i<len;i++){
if((a[i]+a[len-1])>sum){
i=0;
len--;
} else if((a[i]+a[len-1])== sum){
temp=1;
break;
}
}
if(temp==1){
System.out.println(true+"");
} else {
System.out.println(false+"");
}
}
}
This is working perfectly fine
#include<stdio.h>
#include<conio.h>
struct data
{
int a,b;
};
struct data check(int arr[],int n)
{
int i,j,k,temp,flag=0,count=0;
struct data result;
int sum1=arr[0]+arr[1];
int sum2=0;
while(sum1!=sum2 && count<n)
{
for(i=0;i<n;i++)
{
printf("%d\t",arr[i]);
}
printf("\n");
getch();
if(flag==1)
{
for(i=0;i<n;i++)
{
if(i==0)
temp=arr[i];
arr[i]=arr[i+1];
if(i==(n-1))
arr[i]=temp;
}
flag=0;
count++;
for(i=0;i<n;i++)
{
printf("%d\t",arr[i]);
}
printf("\n");
getch();
}
else
{
flag=0;
count++;
}
for(i=0;i<3 && flag==0 ;i++)
{
sum2=0;
sum1=arr[0]+arr[1];
for(j=2;j<n;j++)
{
sum2=arr[j]+sum2;
}
if(sum1!=sum2)
{
for(k=1;k<n;k++)
{
if(k==1)
temp=arr[k];
arr[k]=arr[k+1];
if(k==(n-1))
arr[k]=temp;
}
}
}
flag=1;
for(i=0;i<n;i++)
{
printf("%d\t",arr[i]);
}
printf("\n");
getch();
}
if(sum1==sum2)
{
result.a=arr[0];
result.b=arr[1];
return result;
}
else
{
result.a=0;
result.b=0;
return result;
}
}
void main()
{
struct data res;
int *arr;
int i,num1,num2,n;
clrscr();
printf("Enter no. elements to enter in an array:");
scanf("%d",&n);
arr=(int *)malloc(n,sizeof(int));
for(i=0;i<n;i++)
{
printf("Enter element %d:",i+1);
scanf("%d",&arr[i]);
}
res=check(arr,n);
num1=res.a;
num2=res.b;
if(num1!=0 && num2!=0)
{
printf("\nThe sum of %d and %d is equal to the rest of elements in array. i.e %d",num1,num2,num1+num2);
}
else
printf("\nNo match found");
getch();
}
public class Checksum{
public boolean toSum(int arr[])
{
int length= arr.length;
int check ,sum;
for(int i =0; i<length;i++)
{
for(int j=i+1;j<length;j++)
{
sum = 0;check =0;
check = arr[i] + arr[j];
for(int k=0;k<length;k++)
{
if(k == i || k == (j))
{
//do nothing
}
else
{
sum+= arr[k];
}
}
if(check == sum)
{
return true;
}
}
}
return false;
}
public static void main(String []args){
Checksum cs = new Checksum();
int arr[] = {2,11,5,1,4,7};
if(cs.toSum(arr) == true)
{
System.out.println("yes");
}
else
System.out.println("no");
}
}
public class Checksum{
public boolean toSum(int arr[])
{
int length= arr.length;
int check ,sum;
for(int i =0; i<length;i++)
{
for(int j=i+1;j<length;j++)
{
sum = 0;check =0;
check = arr[i] + arr[j];
for(int k=0;k<length;k++)
{
if(k == i || k == (j))
{
//do nothing
}
else
{
sum+= arr[k];
}
}
if(check == sum)
{
return true;
}
}
}
return false;
}
public static void main(String []args){
Checksum cs = new Checksum();
int arr[] = {2,11,5,1,4,7};
if(cs.toSum(arr) == true)
{
System.out.println("yes");
}
else
System.out.println("no");
}
}
publicclassChecksum{
publicbooleantoSum(intarr[])
{
intlength=arr.length;
intcheck,sum;
for(inti=0;i<length;i++)
{
for(intj=i+1;j<length;j++)
{
sum=0;check=0;
check=arr[i]+arr[j];
for(intk=0;k<length;k++)
{
if(k==i||k==(j))
{
//donothing
}
else
{
sum+=arr[k];
}
}
if(check==sum)
{
returntrue;
}
}
}
returnfalse;
}
publicstaticvoidmain(String[]args){
Checksumcs=newChecksum();
intarr[]={2,11,5,1,4,7};
if(cs.toSum(arr)==true)
{
System.out.println("yes");
}
else
System.out.println("no");
}
}
Sum of 2 elements (S1)=Sum of rest of elements (S2)
- vgeek July 05, 2014So total sum of array S=S1+S2 or S=2S1 so S1=S/2
Now the problem remains of finding two numbers with sum of S1 or S/2.
This can be done as find the sum of whole array and from there get S1 as S/2 and further proceed as:
1. Sort the array in O(nlogn).
For every element arr[i]
a. Binary search for S1-arr[i] in array from i+1 to n-1
b. If element exists then elements found are arr[i] and S1-arr[i].
Complexity: O(nlogn) for sorting and for doing binary search for n elements in logn time which takes total time of O(nlogn)
2. Use self balancing bst (avl trees)
a. Insert all the elements in avl tree. If element is already present then insert it into the left side of the already present element.
b. For each arr[i], search for S1-arr[i] in avl tree. If found then we get our two elements
Complexity: O(nlogn) again.
3. Use hashing.
a. Take a hash table and keep on indexing the elements like hash[arr[i]] to be 1.
b. For every arr[i] if hash[S1-arr[i]] is 1 then we have found our two elements
Complexity: O(n)