Pair of numbers in array

[1vf9z8AR]

Question-
https://www.hackerearth.com/practice/data-structures/hash-tables/basics-of-hash-tables/practice-problems/algorithm/perfect-pair-df920e90/

Summary of question: Find the number of pairs which add up to a perfect square or
a perfect cube.

Issue-
My answer > correct answer

My answer is correct for test cases but not for the other big cases.

  #include<iostream>
#include<vector>
using namespace std;
int main()
{
    vector<int>sqcb;
    sqcb.push_back(0);
    sqcb.push_back(1);
    for(int i=2;i<=10;i++)
    {
        sqcb.push_back(i*i);
        sqcb.push_back(i*i*i);
    }
    for(int i=11;i<=31;i++)
        sqcb.push_back(i*i);
    int t;
    cin>>t;
    while(t>0)
    {
        int freq[1001];
        for(int i=0;i<=1000;i++)
        {
            freq[i]=0;
        }
        int n,temp;
        cin>>n;
        for(int i=0;i<n;i++)
        {
            cin>>temp;
            freq[temp]++;
        }
        long long int ans=0;
        for(auto x:sqcb)
        {
            for(int i=0;i<=x/2;i++)
            {
                if(x-i==i)
                {
                    ans+=(freq[i]*(freq[i]-1))/2;
                }
                else
                {
                    ans+=freq[x-i]*freq[i];
                }
            }
        }
        cout<<ans<<endl;
        t--;
    }
    return 0;
}

[jonnin]

My answer is correct for test cases but not for the other big cases.

well, does anything overflow? What is the largest value you have for i ? What is the largest value of int on your system? Is i*i*i bigger than this?

[1vf9z8AR]

@jonnin

i*i*i in code is maximum 1000
i*i in code is maximum 961

these are within int

[jonnin]

ok, what value gives an incorrect answer?

[1vf9z8AR]

@jonnin

test cases are huge!!. Let me try and paste.

10
100
36 15 75 31 49 60 21 9 43 56 23 89 6 55 44 3 44 13 39 98 19 56 38 74 84 83 93 44 62 91 30 24 22 23 5 23 29 12 56 6 2 83 68 92 16 17 68 89 1 1 90 55 9 21 9 93 32 29 66 53 7 46 64 89 4 97 65 59 98 80 58 86 15 35 28 6 23 74 52 63 56 23 45 29 32 54 11 14 44 64 53 23 89 4 27 81 6 97 40 59
100
81 82 8 49 26 40 9 32 30 55 73 34 58 57 15 42 64 41 2 62 62 33 19 99 24 39 5 89 33 79 92 42 95 24 82 8 59 45 80 56 100 83 18 35 2 2 27 77 86 68 83 63 37 81 30 38 45 43 94 30 14 43 51 40 37 64 14 64 63 46 62 12 51 52 82 97 8 36 12 9 10 74 34 79 97 36 99 4 7 73 65 81 75 89 10 56 68 30 69 23
100
37 64 22 23 27 29 30 70 79 78 93 16 22 13 81 10 26 59 68 53 79 77 36 47 7 68 44 5 18 97 100 56 73 94 14 60 32 31 29 38 49 22 46 45 41 33 30 30 81 23 42 44 57 34 66 17 42 31 71 19 86 57 88 65 21 77 99 86 14 77 71 35 64 88 43 30 94 70 94 40 72 89 61 19 25 69 77 62 11 88 84 45 18 8 82 94 14 5 22 40
100
55 72 99 29 52 75 53 2 36 80 95 8 8 15 22 58 39 95 83 89 90 60 92 34 78 73 15 64 99 82 39 59 20 78 87 96 88 39 66 96 16 94 51 44 9 50 6 29 49 54 60 60 43 3 85 94 54 33 56 70 36 75 46 58 52 71 57 46 44 63 79 94 61 3 62 55 3 93 47 27 46 38 45 65 37 93 29 86 37 6 46 48 64 13 33 61 12 45 42 21
100
1 90 51 55 72 40 56 41 41 6 45 96 87 43 39 71 57 79 11 80 100 53 37 52 55 13 30 92 8 90 95 53 30 1 48 17 10 12 55 26 53 20 77 5 20 100 14 79 51 60 97 82 31 31 64 82 44 25 44 70 54 69 39 4 73 5 94 12 12 31 74 3 6 86 65 47 30 81 70 88 8 70 23 36 23 65 34 44 55 12 57 84 15 79 21 68 73 53 41 31
100
36 75 22 49 12 60 89 95 2 86 10 9 17 46 79 55 59 81 29 16 77 24 18 47 71 42 5 66 63 18 72 2 16 11 4 6 30 71 42 67 58 74 57 99 9 52 54 41 10 60 13 49 56 74 41 6 58 38 29 12 61 69 37 29 38 85 1 39 82 52 82 83 63 33 16 73 10 41 18 73 37 49 85 24 54 57 50 98 41 39 71 75 100 76 35 20 92 84 55 79
100
46 99 18 77 83 78 82 92 56 66 7 47 56 48 94 83 95 10 10 25 1 57 94 92 65 5 13 32 26 16 89 6 77 62 24 24 74 26 43 77 21 54 31 25 39 47 43 30 95 80 1 81 21 36 52 45 64 79 48 9 8 14 98 70 18 50 84 53 14 66 94 67 1 83 59 56 78 41 28 88 10 88 66 94 4 1 57 85 11 33 98 79 8 7 3 19 42 35 67 79
100
68 74 76 13 18 39 97 14 73 3 72 52 14 25 12 64 31 99 5 84 14 3 9 19 61 15 69 63 4 38 39 51 45 36 46 96 78 41 9 3 19 92 32 89 82 24 47 92 100 11 58 73 69 32 49 46 97 37 14 91 27 49 87 13 39 35 80 31 46 3 7 44 35 53 59 23 86 36 92 16 78 46 33 81 49 53 45 45 48 100 2 20 63 20 51 77 72 10 59 31
100
89 19 30 77 13 57 94 77 74 83 69 58 73 60 68 82 31 37 16 84 64 15 67 12 93 5 9 37 81 79 19 18 98 88 45 99 24 2 14 97 89 56 29 31 8 34 94 98 49 45 27 43 73 46 39 98 11 93 13 58 30 58 84 56 80 86 18 18 32 93 38 3 1 2 74 22 9 26 37 44 15 3 6 5 92 51 83 53 37 45 18 10 65 7 67 42 88 4 89 52
100
11 65 60 18 89 95 23 27 50 60 57 84 65 35 92 67 66 57 25 64 8 71 27 11 10 30 54 57 53 29 52 32 16 75 74 29 8 44 8 29 32 24 74 19 16 56 87 7 79 30 68 91 41 26 67 62 28 3 3 80 99 37 63 69 23 71 91 48 50 66 43 50 62 30 60 1 43 10 60 74 85 78 39 70 11 52 13 96 16 51 84 59 34 44 41 63 30 87 22 19

[Nooboob]

I am having trouble understanding your code...

vector<int>sqcb;
    sqcb.push_back(0);
    sqcb.push_back(1);
    for(int i=2;i<=10;i++)
    {
        sqcb.push_back(i*i);
        sqcb.push_back(i*i*i);
    }
    for(int i=11;i<=31;i++)
        sqcb.push_back(i*i);

can you please explain use of this ??

Also please explain your code or at least add comments to it for others to understand it.

[dhayden]

From the constraints on the problem page: 1 ≤ A_i ≤ 10³. So the largest sum is 2000, not 1000. So the loop at line 12 should go to 12 and the loop at line 14 should go to 44.

Line 39 is wrong. The problem states "a pair where (A_i + A_j) is a perfect square or a perfect cube and i ≠ j."