How to optimize this code for getting rid of 'time limit exceeded' problem?

Question

I have given the problem link below. What I can't figure out is how to optimize this code so that I can make this program run within 1 sec and don't get a TLE.

Problem link: https://codeforces.com/contest/1527/problem/A

My code:

#include <bits/stdc++.h>

using namespace std;

int rett(int l, int sum)
{
    sum = l & (l - 1);
    if (sum != 0) {
        rett(l - 1, sum);
    }
    else {
        cout << (l - 1) << endl;
    }
}

int main()
{

    int t, f = 0;
    int x;
    cin >> t;
    int i = 0;
    while (i < t) {
        cin >> x;

        int sum = 0;
        rett(x, sum);
        i++;
    }

    return 0;
}

you can simply write down what happens in every step, you would found out pretty fast. — apple apple, May 20 '21 at 18:06
BTW, most of the TLE (Time Limit Exceeded) issues are due to the wrong algorithm. Rarely will optimization get the execution time under the time limit. — Thomas Matthews, May 20 '21 at 18:27
Undefined behavior (severity: nasal demons): `int rett(` but no `return`. That may be legal in C, in C++ bad things will happen. — , May 20 '21 at 19:03
@Tachanka_07 sorry, now, after I re-read the linked problem, I realize even if your code is correct it would still TLE. (and your code do provide correct result even though it's wrong (judge by `sum`) ) — apple apple, May 21 '21 at 17:07

score 0 · Answer 1 · answered May 20 '21 at 19:38

The recursive approach is not the most efficient (more so since an unnecessary second argument is passed), but that's certainly not the reason for the TLE. Taking each single number from x backwards can cause a lot of unneeded operations, since l & (l - 1) can yield a number well below l, and values above the result need not be taken into account; hence we can replace rett(l - 1, sum) with rett(sum, sum) and thereby limit the number of invocations to the number of set bits in x.

score 0 · Answer 2 · answered May 20 '21 at 20:04

I think the solution they are looking for is find the highest set bit in the number, find a new number that has that bit unset and all lower bits set.

For example like this:

int foo(int x) {
    x |= x>>1;
    x |= x>>2;
    x |= x>>4;
    x |= x>>8;
    x |= x>>16;
    x >>= 1;
    return x;
}

If this makes no sense to you, you may be better off finding some other way to practice than that contest thing.

apple apple · Answer 3 · 2021-05-21T18:50:03.283

First of all, let me fix the code* you currently have (would still TLE)

void rett(int l, int sum) // void
{
    sum = sum & (l - 1); // use sum
    if (sum != 0) {
        rett(l - 1, sum);
    }
    else {
        cout << (l - 1) << endl;
    }
}

// also change the invocation
rett(x, x);

*by accident, the answer n is actually the first one that satisfy (n+1 & n) == 0 (which your current code does).

if (x & x-1 & x-2 & ... & n) == 0 then x and n-1 cannot share highest set bit
and we know that the first number n that do not share the highest set bit with x (say 1xxxxx) is the number that with all lower bits set (say 011111)
at the same time n+1 would only contain that bit (sat 10000)
which make it pretty clear that n+1 & n = 0 and x & ... & n+1 & n = 0

since n is the max number possible (by 1.), we got the answer

where n = (1 << highest set bit) - 1

for how to find highest set bit you can refer to this answer, although just a guess, scan through the bits would probably sufficient

How to optimize this code for getting rid of 'time limit exceeded' problem?

3 Answers3