Why My Code Is Not Working For Values Greater Than N=508?

Question

Code for generating a multiplication table from 1 to n and to find the frequency of any given number x

Program Is Coded In C++

#include<iostream>
using namespace std;

int main() {
    long long n,i,j,x,count=0;
    cin>>n>>x;//n is the number till which a table will generate from 1 to n,x is the number whose frequency is to be calculated
    long long a[n][n];//creating a 2-D array 
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            a[j][i]=(j+1)*(i+1);//filling the table column-wise
        }
    }
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            if(a[i][j]==x)//searching for x
            count++;//increasing the counter as x appears.
        }
    }
    cout<<count;//printing the frequency of x

}

1.: why uppercase and bold? 2. what **exactly** isn't working? 3. c++ doesn't support dynamic array-creation like this, thus this won't even compile — , Sep 10 '15 at 19:01
Many systems have a small limit on the size of a stack frame, and a 509x509 local array may be exceeding that limit. You should use dynamic allocation or `std::vector` for large arrays. — Barmar, Sep 10 '15 at 19:10
Do you really need to fill in the table? You can count the frequency of `x` in the first loop, without putting all the values into a table. — Barmar, Sep 10 '15 at 19:21
`long long a[n][n];` is not standard C++ when `n` is not a constant expression. You should use a C++ container class. — crashmstr, Sep 10 '15 at 19:31
GCC has an extension for non-constant array bound specifiers. Thus, `long long a[n][n]` will compile in GCC. — owacoder, Sep 10 '15 at 20:27
@πάντα ῥεῖ - No. I was simply highlighting that, although non-portable, that code sample *would* compile on some compilers, e.g. GCC. — owacoder, Sep 10 '15 at 23:50
@Paul **UPPERCASE AND BOLD** Just to catch your attention which i certainly did :).What isn't working is that in my code i have implemented a search algorithm to count the frequency of x whose complexity is O(n^2).I need a search algorithm so implemented such that it would find x for any input of n from 1 to 10^5 And C++ does support dynamic array-creation as the code works for any value of n less than 509.Link to the problem is http://codeforces.com/problemset/problem/577/A — Dushyant Pratap Singh, Sep 11 '15 at 22:07
@Barmar Yes I Can.I'm a beginner at competitive programming so when i saw this problem in a competition at codeforces i skipped out the simple and elegant solution which you just stated and just like a BULL coded what came first in my mind.I was looking for a search algorithm which would find x for any input lying of n, 1<=n<=10^5 and count it.I know the complexity of the program is O(n^2) but i need to know any other search algorithm which can work in this program within the given constraints.Thanks For Your Help Though :).Link to the problem codeforces.com/problemset/problem/577/A — Dushyant Pratap Singh, Sep 11 '15 at 22:08
@Barmar Thanks for editing the question,it does make sense now :) I'm new to stackoverflow too. — Dushyant Pratap Singh, Sep 11 '15 at 22:18

score 0 · Answer 1 · edited May 23 '17 at 11:44

comments already cover most of the issue. I probably shouldn't reward such a badly-asked question with an answer, but I was curious about a couple things and tried them out.

On a standard install of 64bit Ubuntu 15.04:

$ ulimit -a
core file size          (blocks, -c) 0
data seg size           (kbytes, -d) unlimited
scheduling priority             (-e) 0
file size               (blocks, -f) unlimited
pending signals                 (-i) 31440
max locked memory       (kbytes, -l) 64
max memory size         (kbytes, -m) unlimited
open files                      (-n) 1024
pipe size            (512 bytes, -p) 8
POSIX message queues     (bytes, -q) 819200
real-time priority              (-r) 0
stack size              (kbytes, -s) 65536
cpu time               (seconds, -t) unlimited
max user processes              (-u) 31440
virtual memory          (kbytes, -v) unlimited
file locks                      (-x) unlimited

Growing the stack to more than 64MiB will generate a segfault. I could increase the stack limit if I really wanted to, but it would be better to change the program.

$ bc -l
sqrt(65536*1024/8)
2896.30937574009865994585
$ for ((i=2894 ; i < 2899 ; i++)); do 
    echo $i;
    printf '%s\n' "$i" 10000 | ./a.out || break; 
    echo; 
 done  # extra echo because your code fails to print a newline
2894
21
2895
21
2896
Segmentation fault (core dumped)

Your system seems to have a default stack limit of 2M (5072*8 is just under, 5082*8 is just over).

C++ doesn't support variable-length arrays the way ISO C99 does. However, GNU C++ does support it. It's not a good idea for big arrays.

The C++ way to do this would be with a std::vector, and emulate the 2D array by doing the index calculation yourself. (Don't make a vector of vectors unless you need some rows longer than others)

When filling the array, if the inner loop is over columns (i.e. the inner loop varies the 2nd index), gcc can auto-vectorize it (use -march=native). Just interchanging for lines, rather than changing the assignment, has the desired effect.

Unfortunately, it doesn't run faster for large problems, because memory is the bottleneck. (imul with a throughput of one 64bit result per cycle can saturate main memory just fine. You'd get a speedup if your matrix fit in cache.)

Of course, for this algorithm, actually storing the multiplication table in a 2D array is not useful at all. Generate values on the fly and compare / increment. If you want to be able to answer repeated queries about the frequency of other numbers, loop and increment hashtable[i*j]. Use a std::unordered_map for the hash table.

Since multiplication has special properties, you can take advantage of this to compute the number of ways that i*j can be equal to x. Factor x into its prime factors, then count the ways these prime factors can be split into two groups. Don't forget to account for duplicates, e.g. 2*2*2*7 has (2*2) * (2*7) as one of its possible arrangements, but it doesn't matter which of the three 2s is grouped with the 7.

The brute force method is useful for testing the factoring method, which I will leave as an exercise for the reader.

I admit the question isn't framed right and doesn't make quite sense.I'm new to the programming world and can't actually understand how to implement an algorithm which works for all type of inputs Like N=10,000.Thanks for the answer though :) — Dushyant Pratap Singh, Sep 11 '15 at 21:48
@DushyantPratapSingh: dynamically allocating 2D arrays: http://stackoverflow.com/a/936815/224132 and http://stackoverflow.com/a/28841507/224132. In GNU C++, you might be able to just use `new` with 2D arrays that aren't a compile-time constant, like http://stackoverflow.com/a/16239446/224132 suggests. — Peter Cordes, Sep 11 '15 at 22:42

Why My Code Is Not Working For Values Greater Than N=508?

1 Answers1