-2

I tried to solve the problem but my code still contains some bugs. Why isn't it running?

Here is the link of the question website: https://www.hackerearth.com/practice/data-structures/hash-tables/basics-of-hash-tables/practice-problems/algorithm/pair-sums/?

    #include <iostream>
    #include <bits/stdc++.h>
    using namespace std;

    const int n = 1e7 + 10;
    int hsh[n];

    int main()
    {
        int n, k;
        cin >> n >> k;
        int A[n];
        for (int i = 0; i < n; i++)
        {
            cin >> A[i];
        }
        for (int i = 0; i < n; i++)
        {
           hsh[A[i]] = k - A[i];
        }
        int t = 0;
        for (int i = 0; i < n; i++)
        {
            if (hsh[A[i]] == k - hsh[hsh[A[i]]])
            {
                cout << "YES";
                t = 1;
                break;
            }
        }
        if (t == 0)
        {
            cout << "NO";
        }

        return 0;
    }
mkrieger1
  • 19,194
  • 5
  • 54
  • 65
Aryan Thakur
  • 3
  • 2
  • 1
    Do you know about debugger exist for exactly the same reason? Trust me its perfect time to learn how to use a debugger. basically debugger help you run to your program step by step. – foragerDev Oct 04 '22 at 18:30
  • Why do you think `A[i]` is a valid index for the `hsh` array, as evidenced by expressions like `hsh[A[i]]`? Also, you don't need `hsh`, just get rid of it. Also, the fact that you named it `hsh` make me think you might be confused, because it's not a hash table. – David Grayson Oct 04 '22 at 18:30
  • @DavidGrayson These coding challenges often say in what range the input lies. So it could very well be that the input values are guaranteed to never exceed `1e7 + 9`. But there is much cringe in this code: the variable `n` is both a global and local variable, the use of the [non-standard ``](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h)... – G. Sliepen Oct 04 '22 at 18:41
  • I'm surprised it even lets you make an array with ten million elements in it. – Nathan Pierson Oct 04 '22 at 19:04
  • @David Grayson buddy you said A[is] is an invalid index, why do you think so? why can't it be? and Yes I kinda used the hash table method, but can't say it is a hash table, is it wrong? – Aryan Thakur Oct 05 '22 at 05:35
  • @G. Sliepen buddy, thanks for pointing out my syntactical error, I should've used block N instead of n for 1e7+10. But can you please help me with the logical error, cuz that's the main issue i am facing here. – Aryan Thakur Oct 05 '22 at 06:12
  • 1
    @NathanPierson If it's a global variable it can basically be as large as you want and it will still compile. On Linux, when you try to execute it, it has to fit in RAM or else you get a segmentation fault. But 40 megabytes is not much these days. – G. Sliepen Oct 05 '22 at 09:34
  • A[i] could be negative or larger than n-1. If so, it would be an invalid index for that array. – David Grayson Oct 05 '22 at 15:17

1 Answers1

0

The problem is that while hsh[A[i]] is always valid, hsh[hsh[A[i]] is not. Consider the following input:

1 1
10000

This does the following:

A[0] = 10000;
...
hsh[10000] = 1 - 10000; // = -99999
...
if (hsh[10000] == 1 - hsh[-99999]) {...}

So your code is reading out of bounds of the array hsh[]. Make sure you check first if hsh[A[i]] >= 0.

Note that your code is more complicated than necessary; you can do a single loop over the input to check if there is a matching pair:

#include <iostream>

static constexpr int max_k = 2e6;
static bool seen[max_k + 1];

int main()
{
   int n, k;
   std::cin >> n >> k;

   for (int i = 0; i < n; ++i)
   {
     int A;
     std::cin >> A;

     if (A <= k && seen[k - A]) {
       std::cout << "YES\n";
       return 0;
     }

     seen[A] = true;
   }

   std::cout << "NO\n";
}
G. Sliepen
  • 7,637
  • 1
  • 15
  • 31