Find existence of two integers in sequence that sum(a, b) = target

user_12278291 0
Viewed 88

The task is:

Input from file input.txt and output to file output.txt The first line is target number. The second line is sequence of positive integers in range 1 to 999999999.

If any two of these integers in sum equals to the target the program has to output 1 otherwise 0.

Example:

5
1 7 3 4 7 9

Output: 1

There is my program. It pass 5 tests and fails the 6th - wrong result. I need help to find the bug or rewrite it.

#include <stdio.h>

int main() {
    FILE *fs = fopen("input.txt", "r");
    int target;
    fscanf(fs, "%d", &target);
    unsigned char bitset[1 + target / 8];

    int isFound = 0;

    for (int number; !isFound && fscanf(fs, "%d", &number) == 1;) {
        if (number <= target) {
            const int compliment = target - number;
            isFound = (bitset[compliment / 8] & (1 << (compliment % 8))) > 0;
            bitset[number / 8] |= 1 << (number % 8);
        }
    }
    fclose(fs);

    fs = fopen("output.txt", "w");
    fprintf(fs,"%d", isFound);
    fclose(fs);

    return 0;
}
c
2 Answers

In your code, you forget to clear the local array, so you get undefined behavior and incorrect results. Note that variable sized arrays cannot be initialized with an initializer so you should use memset to clear this array.

The problem with this approach is target could be very large, up to 1999999997, which makes it impractical to define a bit array of the necessary size with automatic storage. You should allocate this array with calloc() so it is initialized to 0.

Here is a modified version:

#include <limits.h>
#include <stdio.h>

int main() {
    FILE *fs = fopen("input.txt", "r");
    unsigned long target, number;  /* type long has at least 32 bits */
    int isFound = 0;

    if (!fs || fscanf(fs, "%lu", &target) != 1)
        return 1;

    if (target <= 1999999998 && target / 8 < SIZE_MAX) {
        unsigned char *bitset = calloc(1, 1 + target / 8);
        if (bitset != NULL) {
            while (!isFound && fscanf(fs, "%lu", &number) == 1) {
                if (number <= target) {
                    unsigned long complement = target - number;
                    isFound = (bitset[complement / 8] >> (complement % 8)) & 1;
                    bitset[number / 8] |= 1 << (number % 8);
                }
            }
            free(bitset);
        }
    }
    fclose(fs);

    fs = fopen("output.txt", "w");
    fprintf(fs, "%d", isFound);
    fclose(fs);

    return 0;
}

For very large target values, a different approach can be used, using a hash table:

  • read the next value number
  • if target-number is in the hash table, found=1, stop
  • if not, store number in the hash table
  • continue
user_45932670

At least this problem:

Code attempts to read uninitialized data

bitset[] not initialized.

isFound = (bitset[compliment / 8] ....

Suggest initializing:

 unsigned char bitset[1 + target / 8];
 memset(bitset, 0, sizeof bitset);
user_24103590
Related