Data Structures and Algorithm Analysis Exercise 7.53(a) and (b) with “sum” on li

Question

Data Structures and Algorithm Analysis

Exercise 7.53(a) and (b) with “sum” on line 2 of the problem statement replaced with “difference”.

We are given an array that contains N numbers. We want to determine if there are two numbers whose sum equals a given number K. For instance, if the input is 8, 4, 1,6, and K is 10, then the answer is yes (4 and 6). A number may be used twice Do the following a. Give an O(N2) algorithm to solve this problem. b. Give an O(N log N) algorithm to solve this problem. (Hint: Sort the items first. 7.53 After that is done, you can solve the problem in linear time.)

Explanation / Answer

with O(n2) time -

#include<stdio.h>
int main()
{
   int n , i ,flag;
   printf("Enter n ");
   scanf("%d",&n);
   int a[n],j;
   printf("Enter %d elements of the array ",n);
   for(i=0;i<n;i++)
   {
   scanf("%d",&a[i]);
   }
   printf("Enter the sum to check existence in the array as the sum of the elements ");
   int k ;
   scanf("%d",&k);
   int b[n*n];
   int l=0;
   for(i=0;i<n;i++)
   {
   for(j=0;j<n;j++)
   {
       b[l]=a[i]+a[j];
   l++;
   }
   }
   for(i=0;i<l;i++)
   {
       if(k==b[i])
       {
           printf("yes");
           flag=1;
           break;
   }
}
if(flag!=1)
{
printf("no");
}  
   return 0;
}

with O(nlogn) time -

#include <stdio.h>
#include<stdlib.h>
void quickSort(int *, int, int);
int fun(int a[], int n, int k);
int partition(int A[], int si, int ei);
void swap(int *a, int *b);
int main()
{
int n , i , k ;
printf("Enter n ");
scanf("%d",&n);
int a[n];
printf("Enter %d elements to check the existence of sum of two numbers in the array ",n);
  
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
   printf("Enter the value of sum as k ");
   scanf("%d",&k);
   if(fun(a, n, k))
       {
       printf("yes ");
   }
   else
   {
       printf("no ");
}
   return 0;
}

int fun(int a[], int n, int k)
{
   int l, r;

   /* Sort the elements */
   quickSort(a, 0, n-1);

   /* Now look for the two candidates in the sorted
   array*/
   l = 0;
   r = n-1;
   while (l < r)
   {
       if(a[l] + a[r] == k)
           return 1;
       else if(a[l] + a[r] < k)
           l++;
       else // a[i] + a[j] > k
           r--;
   }
   return 0;
}

void swap(int *a, int *b)
{
   int temp;
   temp = *a;
   *a = *b;
   *b = temp;
}

int partition(int a[], int si, int ei)
{
   int x = a[ei];
   int i = (si - 1);
   int j;

   for (j = si; j <= ei - 1; j++)
   {
       if(a[j] <= x)
       {
           i++;
           swap(&a[i], &a[j]);
       }
   }
   swap(&a[i + 1], &a[ei]);
   return (i + 1);
}

void quickSort(int a[], int si, int ei)//si is starting index and ei is ending index
{
   int pi; //index to make partition
   if(si < ei)
   {
       pi = partition(a, si, ei);
       quickSort(a, si, pi - 1);
       quickSort(a, pi + 1, ei);
   }
}

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.