CODEWITHSUNDEEP
algorithmbit-manipulationbitwise-operatorsxor
user12183818
user12183818

Reputation:

How to solve following bitwise xor problem in O(n)

Given an binary string 100000... of size 'm' on day 0 , For each subsequent day, the updated value at each index >= 1 is given by xor of the value of (i-1)th index and ith index on the previous day . Print the binary string on nth day . where 1<=n,m<=1e5.

I am able to see some pattern after writing down the string for several days but not able to make it concise .

Following is the link

Read the first question of coding round.

question is slightly different from the link given (since that question can be solved by brute force)

Upvotes: 0

Views: 471

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59368

The construction is the same as Pascal's Triangle, so on day n, the ith index will hold C(n,i)%2, where C(n,i) is the binomial coefficient.

C(n,i) = n!/(i!(n-i)!)

To figure out whether or not that is even, we only need to know the number of factors of 2 in n!, i!, and (n-i)!. Iff i>0 && i<n && num2s(n!) > num2s(i!) + num2s((n-i)!) then C(n,i) is even and C(n,i)%2 = 0

Since you'll have to spend O(n) time anyway to calculate the string, you might as well build an array of num2s(x!) for all 1 to n. That is easy, since num2s(x!) = num2s(x)+num2s((x-1)!)

Here's an implementation in java:

static String pascalString(int n)
{
    int[] num2s = new int[n+2];

    //calculate number of 2 factors in 1...n
    num2s[0] = num2s[1] = 0;
    for (int i=2; i<=n; ++i) {
        if ((i&1) == 0) {
            num2s[i] = num2s[i/2]+1;
        } else {
            num2s[i] = 0;            
        }
    }

    //convert to number of 2 factors in 1! ... n!
    for(int i=2; i<=n; ++i) {
        num2s[i] += num2s[i-1];
    }

    //calculate C(n,i)%2 for all i
    StringBuilder sb = new StringBuilder();
    for (int i=0; i<=n; ++i) {
        if (i > 0 && i < n && num2s[n] > num2s[i] + num2s[n-i]) {
            sb.append('0');
        } else {
            sb.append('1');
        }
    }
    return sb.toString();
}

Try it here: https://ideone.com/0E99Ge

Upvotes: 1

Related Questions