Find the longest length of sequence of 1-bits achievable by flipping a single bit from 0 to 1 in a number

Question

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 to 1. Write code to find the length of the longest sequence of 1s you could create.

EXAMPLE

Input 1775 (or: 11011101111)

Output 8

— Cracking the Coding Interview (6th edition)

Feedback I am looking for

Here's the list of things I am interested to hear back (in order of significance):

1. Design decisions and improvements (as in "better approach(es) performance- and memory-wise").
2. Code readability.
3. JavaScript (ES6) language idioms.
4. 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.

1. numbersWithSingleZeroFlippedToOneIn(n) function attempts to set a single bit to 1 via bitwise or (|) operator with a 1 shifted to every possible position. If the result of that | application to n does not equal to n itself, it means the bit has changed the state from 0 to 1 and the resulting number should be used in the next step.
2. 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 of 1s (which is determined by making a call to longestSequenceOfOnes(n).
3. The longestSequenceOfOnes(n) function slides from one side of the bit array to another and increments the sequence length by 1 for each observed 1-bit; or resets the sequence length to 0 when a 0-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);
    });
  });
});

Answer 1

I will leave it for others to talk about the code details, because I'm not as up to date with Javascript as I might be. Instead I'm going to focus on the analysis of the algorithm and alternatives.

What you have is technically an \$ O(1) \$ approach on the basis that all your loops are up to a constant 32. However, that's generally uninteresting for analysis so I'll assume the number of possible bits can vary. (i.e. assume instead that the input is an arbitrarily long array of ones and zeroes)

In more conventional analysis, it's \$ O(n^2) \$ in time and space: You have a list of size \$ O(n) \$ coming out of numbersWithSingleZeroFlippedToOneIn and for each element in that list you're running an \$ O(n) \$ function longestSequenceOfOnes. Without changing your core algorithm, you could reduce the space complexity massively by using a generator rather than storing flippedNumbers (an approach that is normally worth considering whenever you create an array to iterate over just once.)

A theoretical lower bound on this problem is \$O(n)\$ because any algorithm must check each bit in the input sequence.

Supposing the task was simpler: find the longest sequence of 1-bits in the number. One way of doing that is to loop over the bits of the number for one pass, keeping track of the last observed zero. When you hit another zero, you check the number of ones between the current and last zero, and compare it to the longest sequence seen thus far.

This approach can be easily adapted to the current problem while remaining an \$O(n)\$ algorithm (and \$O(1)\$ in space). All you'd have to do is keep track of the last two seen zeros, because the ability to flip a single zero to a one is equivalent to the ability to just ignore one zero.

Answer 2

Your unit test looks good. You should add the example from the interview question, just to demonstrate that the code covers this particular case.

{ inputNumber: 1775, expectedResult: 8 },

As others have already said, your code is complicated and inefficient. Have a look at the official Java solutions and the JavaScript solution. Read them carefully and critically since this book is generally full of mistakes. But this time, the Java solution QuestionD contains efficient and short code, while all the other solutions are inefficient.

The general goal of bit manipulation algorithms is to be allocation-free. And if that is possible, it's usually efficient. Your code allocates an array, therefore you should think about a different algorithm. If you don't find one, fine. But at least look for one.

Aside from this criticism, your code looks good. You chose accurate names for the functions, the variables are clearly named, too. The code is nicely split into comprehendable functions, which is all good.

In the unit test, I would have written the large numbers in binary or hexadecimal instead of the complex computations, as these are hard to follow:

0b11111111111111111111111111111111
0xFFFFFFFF
0b01111111111111111111111111111111
0x7FFFFFFF

Unfortunately, JavaScript doesn't allow underscores in number literals, otherwise even the binary literals were readable:

0b1111_1111_1111_1111_1111_1111_1111_1111

Answer 3

Unnecessary storage

Building an array of numbers with one zero flipped is unnecessary for the end result. It's just an intermediary storage of intermediary values.

The intermediary values can be skipped by mapping them directly to more meaningful values: the lengths of the longest sequences of 1s.

And you can do away with the array completely, by keeping tracking of the longest length seen so far.

So the extra storage can be reduced to \$O(1)\$.

Assumptions

This statement represents an assumption about the length of "integer":

const NUMBER_OF_BITS_IN_NUMBER = 32;

It's not necessarily correct. I would interpret the problem differently, in the direction of large scale, by assuming a sequence of bits of arbitrary length.

Counting bits

When counting bits, instead of counting the steps to shift, it's better to "just shift", until some condition.

For example, given some value work, you could loop until the value is 0, and in each step check the value of work & 1 and do what's necessary, and then work >>= 1. This has two benefits:

• The terminating condition is independent from the number of bits: it will work with numbers of any width, and you don't have to know in advance the maximum number of steps to shift.
• The loop terminates as early as possible: smaller numbers will reach 0 faster, no need to iterate further.

Alternatively, if you want to work with a shifted bit as in 1, 2, 4, 8, 16 and so on, you could shift that by one in each iteration as in bit <<= 1, and use a terminating condition based on a numeric comparison of bit and the reference number. This will have the same benefits as the other example above.

Alternative implementation

Similar to what @Josiah suggested, a more efficient alternative would be to track the lengths of the last 2 sequences of 1s, and thereby the longest possible sequence seen so far.

Based on that, and on the above suggestions, I would write like this:

function longestSequenceOfOnesWithOneFlip(n) {
  var work = n;
  var prev = 0;
  var current = 0;
  var longest = 0;

  while (true) {
    if ((work & 1) === 0) {
      longest = Math.max(longest, prev + current);
      if (work === 0) {
        // this is to count numbers like 111 as 1111 -> 4 instead of 3
        if (prev == 0) longest++;
        break;
      }
      prev = current + 1;
      current = 0;
    } else {
      current++;
    }
    work >>= 1;
  }
  return longest;
}

Answer 4

Too complex

As the other answer pointed out your solution is too complex. The number of bits you test in the function longestSequenceOfOnes is proportional to the number of off bits in the value.

For the value 0 you loop inside longestSequenceOfOnes a total of 32 (off bits) * 32 (checks) for a total of 1024 iteration. With the mean number of off bits in any random 32bit int being 16 the mean iteration count (bit checks) is 512.

The whole thing can be done in an average of 31 iterations per value.

Bad testing

Also your testing is very poor. The problem is easily scaled to a different number of bits. For 8 bits you can test all 256 combinations and will give you all possible types of patterns you are looking for.

The ideal test is against a known working algorithm and check every unique combination. IE you dont have to test 0b1111000 if you have tested 0b111100

Example of a quicker test

It only does 8 bits

function findFlipBit(val) {
    var bitPos, possibleBit, count, longest, longestPos;
    if (val === 0) { return 0 }  // early exit
    longest = count = seqCount = bitPos = 0;
    possibleBit = -1; // This hold pos of last found 0 bit between squences
                      // Is set to -1 if last 0 had 0 befoe

    // saves the bit pos and length of sequence
    const isLongest = (count, index = bitPos) => {
        if (count > longest) {
            longestPos = index;
            longest = count;
        }
    }
    // check if next bit is on. If so remember pos of this bit and length
    // of sequence before it.
    const checkNextBit = () => {
        if (val & 2) {
            possibleBit = bitPos;
            count = seqCount;
        } else { possibleBit = -1 }
    }
    while (true) {
        if (val & 1) { seqCount += 1 } // count on bits
        else {
            if (possibleBit === -1) {  // if no possibility found
                checkNextBit();        // check next bit is on
                isLongest(seqCount)    // is the current sequence the longest
            } else {
                isLongest(count + seqCount, possibleBit); // If a possible in between bit 
                                                          // was found add next seq and 
                                                          // see if longest
                checkNextBit();
            }
            seqCount = 0;          // reset sequence count
        }
        // Shift down, there are many ways but remember that in JS
        // 32Bit ints are signed
        val = val / 2 | 0;
        bitPos++;         // count the bit position
        totalItCount ++;  // only for the test counts iterations
        if (val === 0 || bitPos === 8) {
            if (possibleBit > -1) { isLongest(count + seqCount, possibleBit) }
            isLongest(seqCount)
            return longestPos;
        }
    }
}





   /* Demo code and not part of answer code from here down */


const display = [];
var totalItCount = 0;
for(var i = 0; i < 256; i++){
   const result = findFlipBit(i);

   const str =  i.toString(2).replace("-").padStart(8,"0")   
   const str1 = (str.substr(0,7-result) + "^" + str.substr(7-result+1)).replace(/1|0/g,".");

   display.push(str +  " Num : " + i);
   display.push(str1 + " Pos " + result);
 }
 
 log("Test 0 - 255");
 
 log("Total number bit positions : " + (8 * 256));
 
 log("Total number of iterations : " + totalItCount + " : " + (totalItCount / (8 * 256) * 100).toFixed(1) + "%" );
 
 log("Mean iteration count per test : " + (totalItCount / 256).toFixed(2));

 log("Results ^ shows position of flip bit");
 log("====================================");
 display.forEach(log);
 



function log(data){
    showEl.appendChild(Object.assign(document.createElement("div"),{textContent : data}));
}

<code id ="showEl"></code>