Problem Statement
The problem is defined in the book as following:
5.3 You have an integer and you can flip exactly one bit from
0
to1
. Write code to find the length of the longest sequence of1
s you could create.EXAMPLE
Input
1775
(or:11011101111
)Output
8
Feedback I am looking for
Here's the list of things I am interested to hear back (in order of significance):
- Design decisions and improvements (as in "better approach(es) performance- and memory-wise").
- Code readability.
- JavaScript (ES6) language idioms.
- Whatever you find important to say that does not fall into three categories mentioned above.
My approach, design, implementation, and performance description
Both time and space complexity of the solution is O(n)
, where n
is the total count of bits in a bit representation of the integer number. However, I feel there might be some smart approach (or a "trick") that improves the solution.
My code basically consists of three parts.
numbersWithSingleZeroFlippedToOneIn(n)
function attempts to set a single bit to1
via bitwise or (|
) operator with a1
shifted to every possible position. If the result of that|
application ton
does not equal ton
itself, it means the bit has changed the state from0
to1
and the resulting number should be used in the next step.- The numbers from the previous steps are iterated through via
reduce()
function. The seed value is set to-1
which indicates an "unknown" maximal length of sequence of1
s (which is determined by making a call tolongestSequenceOfOnes(n)
. - The
longestSequenceOfOnes(n)
function slides from one side of the bit array to another and increments the sequence length by 1 for each observed1
-bit; or resets the sequence length to0
when a0
-bit is observed. The code actually explains this part better...
Code
const NUMBER_OF_BITS_IN_NUMBER = 32;
function flipToWin(numberToFlip) {
return numbersWithSingleZeroFlippedToOneIn(numberToFlip)
.reduce(
(subresult, flippedNumber) => Math.max(subresult, longestSequenceOfOnes(flippedNumber)),
-1,
);
}
function numbersWithSingleZeroFlippedToOneIn(numberToFlip) {
const flippedNumbers = [];
for (let shift = 0; shift < NUMBER_OF_BITS_IN_NUMBER; shift++)
{
const candidate = numberToFlip | (1 << shift);
const isFlipped = candidate !== numberToFlip;
if (isFlipped)
flippedNumbers.push(candidate)
}
return flippedNumbers;
}
function longestSequenceOfOnes(flippedNumber) {
let longestSequence = 0;
let currentSequence = 0;
for (let position = 0; position < NUMBER_OF_BITS_IN_NUMBER; position++) {
const isBitInPositionSet = flippedNumber & (1 << position);
if (isBitInPositionSet) {
currentSequence += 1;
} else {
longestSequence = Math.max(longestSequence, currentSequence);
currentSequence = 0;
}
}
longestSequence = Math.max(longestSequence, currentSequence);
return longestSequence;
}
Unit tests
import { flipToWin } from '../src/cracking-the-coding-interview/5-bit-manipulation/5-3-flip-to-win';
describe(flipToWin.name, () => {
[
{ inputNumber: 0, expectedResult: 1 },
{ inputNumber: 1, expectedResult: 2 },
{ inputNumber: 2, expectedResult: 2 },
{ inputNumber: 4, expectedResult: 2 },
{ inputNumber: 8, expectedResult: 2 },
{ inputNumber: 16, expectedResult: 2 },
{ inputNumber: 32, expectedResult: 2 },
{ inputNumber: 3, expectedResult: 3 },
{ inputNumber: 5, expectedResult: 3 },
{ inputNumber: 6, expectedResult: 3 },
{ inputNumber: 10, expectedResult: 3 },
{ inputNumber: 12, expectedResult: 3 },
{ inputNumber: 20, expectedResult: 3 },
{ inputNumber: 24, expectedResult: 3 },
{ inputNumber: 48, expectedResult: 3 },
{ inputNumber: (~0 & (~0 << 1)), expectedResult: 32 },
{ inputNumber: (~0 & (~0 << 2)), expectedResult: 31 },
{ inputNumber: (~0 & (~0 << 3)), expectedResult: 30 },
{ inputNumber: (~0 & (~0 << 4)), expectedResult: 29 },
].forEach(({ inputNumber, expectedResult }) => {
it(`Should return length of ${expectedResult} for input number ${inputNumber}.`, () => {
expect(flipToWin(inputNumber)).toEqual(expectedResult);
});
});
});