Given an array of unique numbers and a value, a valid triplet is a set of three numbers (not necessarily continuous in the array) that add up to the value. Write a program to count all valid triplets. Print the number of valid triplets.
Hint: Can you solve this in O(n^2) steps?
Input : First line contains N and Sum (Space separated). Second line contains space separated list of N numbers.
Output: Number of triplets such that sum possible
Constraints:
- 0 < N < 100
- All numbers in the list are unique and between -10^4 to 10^4
- -10^3 < Sum < 10^3
Solution -:
#include<stdio.h>
int main()
{int i,j,k,n,sum,a[100],b=0;
scanf("%d%d",&n,&sum);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
for(k=j+1;k<n;k++)
{
if(sum==(a[i]+a[j]+a[k]))
b++;
}
}
}
printf("%d",b);
return 0;
}
i have tried quadratic algorithm which is in the link https://en.wikipedia.org/wiki/3SUM
ReplyDeletestill i am getting only 75 out of 100.If possible please provide testcsaes which fails this algorithm.
#include
ReplyDelete#define MAXSIZE 20
// A utility function to sort an array using Quicksort
//Implementation of Quick Sort
//A[] --> Array to be sorted
//si --> Starting index
//ei --> Ending index
void quickSort(int A[], int si, int ei)
{
int pi; // Partitioning index
if(si < ei)
{
pi = partition(A, si, ei);
quickSort(A, si, pi - 1);
quickSort(A, pi + 1, ei);
}
}
int find3Numbers(int A[], int arr_size, int sum)
{
int l, r;
// Sort the elements
quickSort(A, 0, arr_size-1);
// Now fix the first element one by one and find the other two elements
int i;
int count = 0;
int d;
for (i = 0; i < arr_size - 2; i++)
{
// To find the other two elements, start two index variables
// from two corners of the array and move them toward each
// other
l = i + 1; // index of the first element in the remaining elements
r = arr_size-1; // index of the last element
while (l < r)
{
if( A[i] + A[l] + A[r] == sum)
{
i++;
count++; //add to the count when a triplet is found
continue;
}
else if (A[i] + A[l] + A[r] < sum)
l++;
else // A[i] + A[l] + A[r] > sum
r--;
}
}
int result = count/3; //I was getting weird results so I tried this
printf("%d", result);
return 0;
}
// These two functions help with the sorting
void exchange(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++;
exchange(&A[i], &A[j]);
}
}
exchange (&A[i + 1], &A[ei]);
return (i + 1);
}
//This is the Main function
int main()
{
int arr[MAXSIZE];
int num;
int n;
int arr_size = sizeof(arr)/sizeof(arr[0]);
int i;
scanf("%d %d",&n,&num);
for (i = 0; i < n; ++i)
{
scanf("%d",&arr[i]);
}
find3Numbers(arr, arr_size, num);
return 0;
}
///////////////////////////
I am getting weird results, can you please point out what did I mess up?
will understand your code and get back to you shortly.
DeleteThank you very much!
Deletebrother code is bit complicated and i m busy for days .please give me some time and i assure you that i will definitely solve your issue.
DeleteThank you very much bro, I have solved the other 3 assignments, I have commented the code, I am having problem mainly in counting the triplets.
DeleteThank you for helping, means a lot.
#include
ReplyDeleteint main(){
int i,j,k,N,q=0,sum,a[100];
scanf("%d %d",&N, &sum);
for(i=0;i<N;++i)
scanf("%d",&a[i]);
for(i=0;i<N-2;++i)
for(j=i+1;j<N-1;++j)
for(k=j+1;k<N;++k)
if((a[i]+a[j]+a[k])==sum)
q++;
printf("%d",q);
return 0;
}
This comment has been removed by the author.
DeleteSaket can you give the solution for Evaluating polynomials, Selection Sort, Closest Numbers too
Deletethen what u'll do
ReplyDelete