C Program to Solve Two Sum Using Brute Force (With Algorithm & Output)

 Introduction

The Two Sum problem is a popular coding interview question where we must find two indices of an array whose values add up to a given target. This program demonstrates a simple brute-force solution in C using nested loops and dynamic memory allocation.

Problem Statement

Given an integer array and a target value, return the indices of the two numbers such that they add up to the target. Each input has exactly one solution, and the same element cannot be used twice. The result should return the indices, not the values. If no solution exists, return NULL.

 Algorithm / Logic Explanation

1. Start the program.

2. Traverse the array using a loop from index 0 to numsSize - 1.

3. Inside this loop, use another loop starting from i + 1 to numsSize - 1.

4. For every pair (i, j), check if nums[i] + nums[j] == target.

5. If condition becomes true:

   • Allocate memory for 2 integers using malloc().

   • Store indices i and j.

   • Set returnSize = 2.

   • Return the result pointer.

6. If no pair is found after checking all combinations:

   • Set returnSize = 0

   • Return NULL.

This approach uses brute-force comparison of all possible pairs.

 Source Code 

Two Sum Function Only

int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    for (int i = 0; i < numsSize; i++) {
        for (int j = i + 1; j < numsSize; j++) {
            if (nums[i] + nums[j] == target) {
                int* result = (int*)malloc(2 * sizeof(int));
                result[0] = i;
                result[1] = j;
                *returnSize = 2;
                return result;
            }
        }
    }
    *returnSize = 0;
    return NULL; 
}

Complete Program (With main Function)

#include <stdio.h>
#include <stdlib.h>

int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    for (int i = 0; i < numsSize; i++) {
        for (int j = i + 1; j < numsSize; j++) {
            if (nums[i] + nums[j] == target) {
                int* result = (int*)malloc(2 * sizeof(int));
                result[0] = i;
                result[1] = j;
                *returnSize = 2;
                return result;
            }
        }
    }
    *returnSize = 0;
    return NULL; 
}

int main() {
    int n, target;

    printf("Enter number of elements: ");
    scanf("%d", &n);

    int *nums = (int*)malloc(n * sizeof(int));

    printf("Enter %d elements:\n", n);
    for(int i = 0; i < n; i++) {
        scanf("%d", &nums[i]);
    }

    printf("Enter target value: ");
    scanf("%d", &target);

    int returnSize;
    int* result = twoSum(nums, n, target, &returnSize);

    if(result != NULL) {
        printf("Indices: %d and %d\n", result[0], result[1]);
        free(result);
    } else {
        printf("No solution found\n");
    }

    free(nums);
    return 0;
}

Sample Input / Output

Input:
Array = {2, 7, 11, 15}
Target = 9

Output:
Indices: 0 and 1

Explanation of Code

The function twoSum() takes four parameters: the integer array, its size, the target value, and a pointer to store the return size. The outer loop runs from index 0 to numsSize - 1. The inner loop starts from i + 1 to avoid checking the same element twice.

Inside the nested loops, we check if the sum of two elements equals the target. If the condition is satisfied, we dynamically allocate memory using malloc() for two integers. These integers store the indices of the matching elements.

We then set *returnSize = 2 because two indices are returned. The function returns the pointer to the allocated memory.

If no pair is found after checking all combinations, the function sets returnSize to 0 and returns NULL.

In the main() function, we test the program with a sample array. If a solution is found, we print the indices and free the allocated memory using free() to prevent memory leaks.

Time Complexity: O(n²)
Space Complexity: O(1)

 Edge Cases / Notes

• If no two elements match the target, the function returns NULL.
• Works with negative numbers.
• Array must contain at least two elements.
• Always free allocated memory to avoid memory leaks.

Conclusion

The Two Sum problem is a fundamental coding interview question that demonstrates array traversal and nested loop logic. This C implementation uses a brute-force method and dynamic memory allocation to return indices efficiently.

Frequently Asked Questions (FAQ)

1. What is the Two Sum problem in C?

The Two Sum problem is a coding challenge where we need to find two indices in an array such that their values add up to a given target. In C, this is commonly solved using nested loops or optimized hashing techniques.

2. What is the time complexity of the brute force approach?

The time complexity of the brute force method is O(n²) because we use two nested loops to compare every pair of elements in the array.

3. Why is malloc() used in this program?

malloc() is used to dynamically allocate memory for storing the two indices that satisfy the target condition. This memory must be freed later to avoid memory leaks.

4. Can this program handle negative numbers?

Yes, this solution works correctly with negative numbers as long as two values add up to the given target.

5. Is this solution suitable for coding interviews?

Yes. The brute force approach is simple and easy to understand, making it ideal for beginners. However, interviewers may also expect an optimized O(n) solution using hashing.

Similar Searches

• Two Sum problem in C with solution
• C program for Two Sum with output
• Two Sum algorithm explanation
• C programming interview questions arrays
• LeetCode Two Sum solution in C
• Brute force array problems in C
• Dynamic memory allocation example in C
• Array pair sum problem in C

Hashtags

#CProgramming

#CodingInterview

#TwoSum

#LearnToCode

#DataStructures

#ProgrammingForBeginners

#ComputerScience

#SoftwareDevelopment

#CodingPractice

#TechEducation

#1printf