Abridged statement

There are $$$N$$$ vertices in the graph where $$$N=2^n$$$ where $$$n$$$ is an integer. An array $$$A$$$ of size $$$M$$$ is given. An edge can be drawn from $$$i$$$ to $$$i\oplus x$$$ ($$$\oplus$$$ represents xor operation) if $$$x\notin A$$$. Print $$$N - 1$$$ edges such that the edges form a tree.

Statement

Issue

The intended solution uses xor basis / gaussian elimination. However, I found some submissions that uses completely different algorithms that ACs all the testcases.

In summary, the code iterates through all the $$$x\notin A$$$, and for each $$$x$$$, iterate through all the vertices $$$v$$$ from $$$0$$$ to $$$n - 1$$$. While $$$v$$$ and $$$v \oplus x$$$ are not connected, connect them and move on to vertex $$$v + 1$$$, otherwise, break. This algorithm runs in $$$O(n)$$$ as it will only connect edges $$$n - 1$$$ times and when it cannot connect edges, it breaks immediately. However, does anyone have a proof that it is correct? Will there be any case where breaking early results in the wrong answer? I tried creating a few test cases by hand and it seems to always generate the correct answer.

REP(x,n){
    if(!inA[x]){
        REP(v,n){
            int a=v,b=(v^x);
            if(find(a)!=find(b)){
                edges.pb({a,b});
                merge(a,b);
            }
            else{
                break;
            }
        }
    }
}

In another submission, a similar idea was used, however, instead of breaking early, it iterated through all the vertices from $$$0$$$ to $$$n - 1$$$ as long as $$$0$$$ and $$$x$$$ are not connected. This clearly results in the correct answer as by looping through all the vertices from $$$0$$$ to $$$n - 1$$$, it will definitely result in at least one edge being created, so $$$n - 1$$$ edges will be created after all iterations. However, it looks as if the algorithm runs in $$$O(n^2)$$$. Why does it not TLE?

for(int x=1;x<n;x++){
    if(!inA[x]) continue;
    if(uf.same(0,x)) continue;
    for(int v=0;v<n;v++) add_edge(v,v^x);
}