# How do we optimise the following operation in single loop

f(i,j) = { i*j if i&j==0

for(i=0;i<=N;i++)
for(j=i; j<=N; j++)
If(i&j==0) sum+=i*j;
Print sum;

I’ve to do in O(N)

Suppose , N=5.
From i=1 to N
When,
i=1 j=1
i=1 j=2
i=1 j=3
i=1 j=4
i=1 j=5
i=2 j=2
i=2 j=3
i=2 j=4…
So on…
And whenever i&j ==0 then ive to sum += i*j.

Constraints : 1<=N<=2* 10^5

No,
Suppose , N=5.
From i=1 to N
When i=1 j=1
i=1 j=2
i=1 j=3
i=1 j=4
i=1 j=5
i=2 j=2
i=2 j=3
i=2 j=4…
So on…
And whenever i&j ==0 then ive to sum += i*j.

In you solution , every time i and j will increment

I didn’t test this with many values…but, it might just work:

#define rows 2
#define columns 3

#include<stdio.h>

void  main()
{

int sum=0,i,j,N=25;

int f[rows][columns]={{4,5},{6,7}};

i=rows,j=columns;

for(int t=0;N >= i*j; t++)
{

i = t / N;
j = t % N;

if(i&j==0) sum+=f[i][j];
}

printf("%d",sum);

}
1 Like

print 0
that’s it
i.e., if( i == 0 and j == 0 )
sum += ij // 00 = 0
so the final answer will be 0
or the value of sum with what you’ve initialized

Ok, let me explain my approach:

The total sum of i can be described as i \cdot \sum{j}, for every valid j. This is just like saying i \cdot S where S is the total sum of powers of two that occur in every j, which when summed up add to j. So we didn’t really change the sum, just the formula that will allow us to work easier.

Let’s think in reverse. For the condition to be fulfilled, no bit that is set in i is set in j.

This means, that you can create a bitmask and set all the bits that are 1 in i to 0 in our mask (since they mustn’t occur, we don’t want to be able to change them). We will create 32 subproblems, for every leftmost set bit, how many times do other bits appear in some j, formally for every i, 0 \leq i < 32.

So for each subproblem, we can start from the left and move towards right and try to set every bit to 1 (excluding the fixed bits). In case the total number exceeds N, set k_{th} bit to 0, otherwise to 1. Do this until we reach the last bit.

Now for every bit in the mask, we conclude that number of times it occurs is actually the same as the binary number we get using suffix of non-fixed bits and add 1 on top of that. This is true for every bit that is set in our current mask.

If you don’t understand what’s going on, let me explain with an example:

Suppose 3_{rd} and 5_{th} bit are fixed in our current mask (0-index based, starting from right). Let N be 21. How many times can each bit in current mask occur. First let us build the mask:

Here’s what the starting mask looks like:

0 _ 0 _ _ _

We can fill the blanks starting from left. We ask ourselves is 2^4 greater than N, no - set 4_{th} bit to 1.

0 1 0 _ _ _

Now we skip 3_{rd} bit and go to the 2_{nd} one. In similar fashion - Is 2^4 + 2^2 greater than N. Yes, yes it is \implies set 2_{nd} bit to 0.

Finally our mask will look something like this:

0 1 0 0 1 1

We can see that if we set 4_{th} bit to 1, total number of times it occurs is 011 + 1 in binary, meaning 4 in decimal. So we add 4 \cdot 2^4 to the total sum. We do the same for other set bits. So in total for this mask we will add:

4 \cdot 2^4 + 2 \cdot 2^1 + 1 \cdot 2^0 to the total sum.

Apply this process for all 32 bits and you get the total of O(N log^2 N) complexity, which just so happens to be enough to fit in 1 second of runtime.

I didn’t do the coding part as I suppose it would be nice practice for you to implement it on your own. Hope I was able to help! 1 Like

That’s certainly not the way to go about it. If (a & b) == 0, that does not necessarilly mean that a and b are both 0. It could be a = 2, and b = 1. Similarly, it could also be a = 5, b = 8, etc.