When working with arrays, solving problems like finding two elements that sum up to a target or three elements with a specific sum is quite common. In this blog post, we’ll explore simple implementations in C for both the two-sum and three-sum problems using both iterative and recursive methods.
Two Sum Problem
Iterative Approach
The two-sum problem involves finding two elements in an array that add up to a given target. Here’s a simple iterative C program to solve the two-sum problem:
#include <stdio.h>
int findTwoSum(int arr[], int n, int target) {
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (arr[i] + arr[j] == target) {
printf("Two elements found: %d and %d\n", arr[i], arr[j]);
return 1; // Found
}
}
}
return 0; // Not found
}
int main() {
int arr[] = {2, 7, 11, 15};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 9;
if (!findTwoSum(arr, n, target)) {
printf("No elements found with the given sum.\n");
}
return 0;
}
Recursive Approach
Now, let’s implement the two-sum problem using a recursive approach:
#include <stdio.h>
int findTwoSumRecursive(int arr[], int start, int end, int target) {
if (start >= end) {
return 0; // Not found
}
if (arr[start] + arr[end] == target) {
printf("Two elements found: %d and %d\n", arr[start], arr[end]);
return 1; // Found
} else if (arr[start] + arr[end] < target) {
return findTwoSumRecursive(arr, start + 1, end, target);
} else {
return findTwoSumRecursive(arr, start, end - 1, target);
}
}
int main() {
int arr[] = {2, 7, 11, 15};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 9;
if (!findTwoSumRecursive(arr, 0, n - 1, target)) {
printf("No elements found with the given sum.\n");
}
return 0;
}
Three Sum Problem
Iterative Approach
Now, let’s move on to the three-sum problem. Here’s an iterative C program to find three elements in an array that sum up to a given target:
#include <stdio.h>
int findThreeSum(int arr[], int n, int target) {
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; j++) {
for (int k = j + 1; k < n; k++) {
if (arr[i] + arr[j] + arr[k] == target) {
printf("Three elements found: %d, %d, and %d\n", arr[i], arr[j], arr[k]);
return 1; // Found
}
}
}
}
return 0; // Not found
}
int main() {
int arr[] = {1, 4, 45, 6, 10, 8};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 22;
if (!findThreeSum(arr, n, target)) {
printf("No elements found with the given sum.\n");
}
return 0;
}
Recursive Approach
Lastly, let’s implement the three-sum problem using a recursive approach:
#include <stdio.h>
int findThreeSumRecursive(int arr[], int start, int end, int target) {
if (start >= end) {
return 0; // Not found
}
int remaining = target - arr[start];
for (int i = start + 1; i <= end; i++) {
if (arr[i] + findTwoSumRecursive(arr, i + 1, end, remaining)) {
printf("Three elements found: %d, %d, and %d\n", arr[start], arr[i], remaining);
return 1; // Found
}
}
return 0; // Not found
}
int main() {
int arr[] = {1, 4, 45, 6, 10, 8};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 22;
if (!findThreeSumRecursive(arr, 0, n - 1, target)) {
printf("No elements found with the given sum.\n");
}
return 0;
}
These implementations provide different perspectives on solving the two-sum and three-sum problems. Depending on the specific requirements and constraints of your application, you can choose the appropriate approach.
Important Notice for college students
If you’re a college student and have skills in programming languages, Want to earn through blogging? Mail us at geekycomail@gmail.com
For more Programming related blogs Visit Us Geekycodes . Follow us on Instagram.
