Bit Manipulation & Tips

[LogicBaron]

i & ~(i-1) : right most bit

[LogicBaron]

Tracking all y that use the bits present in x

1723. Find Minimum Time to Finish All Jobs

This problem is all about the recurrence relation below.

for (all y that use the bits present in x) {
    dp[x][k] = min(dp[x][k], max(dp[x-y][k-1], dp[y][1]))
}

one method is,

// N : The number of digits in a binary number, floor(log2(x)) + 1
for (int y=0; y<(1<<N); y++) {
    if ((x|y) != x) continue;
    dp[x][k] = min(dp[x][k], max(dp[x-y][k-1], dp[y][1]))
}

Here is better soluion for tracking all y that use the bits present in x :

for (int y=x; y>0; y=x&(y-1)) {
    dp[x][k] = min(dp[x][k], max(dp[x-y][k-1], dp[y][1]));
}
/*
x = 11011, then
y = 11011 -> 11010 -> 11001 -> 10011 -> 10010 -> 10001 -> 00011 -> 00010 -> 00001 -> 00000
*/