6

How would I find the longest series of ones in this array of binary digits - 100011101100111110011100

In this case the answer should be = 11111

I was thinking of looping through the array and checking every digit, if the digit is a one then add it to a new String, if its a zero re-start creating a new String but save the previously created String. When done check the length of every String to see which is the longest. I'm sure there is a simpler solution ?

blue-sky
  • 51,962
  • 152
  • 427
  • 752
  • Of course, but only if you don't actually have an array of binary digits. – harold Dec 01 '11 at 11:28
  • FYI, I've just posted a more efficient algorithm over here: http://stackoverflow.com/a/10922528/477037. It's written in Ruby but can easily be adapted. – Stefan Jun 06 '12 at 22:00

4 Answers4

4

Your algorithm is good, but you do not need to save all the temporary strings - they are all "ones" anyway.

You should simply have two variables "bestStartPosition" and "bestLength". After you find a sequence of "ones" - you compare the length of this sequence with saved "bestLength", and overwrite both variables with new position and length.

After you scanned all array - you will have the position of the longest sequence (in case you need it) and a length (by which you can generate a string of "ones").

bezmax
  • 25,562
  • 10
  • 53
  • 84
4

Java 8 update with O(n) time complexity (and only 1 line):

int maxLength = Arrays.stream(bitStr.split("0+"))
  .mapToInt(String::length)
  .max().orElse(0);

See live demo.

This also automatically handles blank input, returning 0 in that case.

Java 7 compact solution, but O(n log n) time complexity:

Let the java API do all the work for you in just 3 lines:

String bits = "100011101100111110011100";

LinkedList<String> list = new LinkedList<String>(Arrays.asList(bits.split("0+")));
Collections.sort(list);
int maxLength = list.getLast().length(); // 5 for the example given

How this works:

  1. bits.split("0+") breaks up the input into a String[] with each continuous chain of 1's (separated by all zeros - the regex for that is 0+) becoming an element of the array
  2. Arrays.asList() turns the String[] into a List<String>
  3. Create and populate a new LinkedList from the list just created
  4. Use collections to sort the list. The longest chain of 1's will sort last
  5. Get the length of the last element (the longest) in the list. That is why LinkedList was chosen - it has a getLast() method, which I thought was a nice convenience

For those who think this is "too heavy", with the sample input given it took less than 1ms to execute on my MacBook Pro. Unless your input String is gigabytes long, this code will execute very quickly.

EDITED

Suggested by Max, using Arrays.sort() is very similar and executes in half the time, but still requires 3 lines:

String[] split = bits.split("0+");
Arrays.sort(split);
int maxLength = split[split.length - 1].length();
Bohemian
  • 412,405
  • 93
  • 575
  • 722
3

Here is some pseudocode that should do what you want:

count = 0
longestCount = 0
foreach digit in binaryDigitArray:
   if (digit == 1) count++
   else:
      longestCount = max(count, maxCount)
      count = 0
longestCount = max(count, maxCount)

Easier would be to extract all sequences of 1s, sort them by length and pick the first one. However, depending on the language used it would probably be only a short version of my suggestion.

Till Helge
  • 9,253
  • 2
  • 40
  • 56
0

Got some preview code for php only, maybe your can rewrite to your language.

Which will say what the max length is of the 1's:

$match = preg_split("/0+/", "100011101100111110011100", -1, PREG_SPLIT_NO_EMPTY);
echo max(array_map('strlen', $match));

Result:

 5
Niels
  • 48,601
  • 4
  • 62
  • 81