Tech Qu: Maximum sub sequence which has equal number of 1s and 0s.

You are given an array ' containing 0s and 1s. Find the maximum sub sequence which has equal number of 1s and 0s.

 

The solution is straight forward (using a long  so testing would be easy).

  • We determine the maximum possible length and use this to shorten the loops.
Code Snippet
  1. public static int Subsequence(long rawdata)
  2.     {
  3.       var data = new BitArray(System.BitConverter.GetBytes(rawdata));
  4.       if (data.Length < 2)
  5.         return data.Length;
  6.       var zCount = 0;
  7.       var oneCount = 0;
  8.       var sb = new StringBuilder();
  9.       foreach (bool datum in data)
  10.       {
  11.         if (datum)
  12.         {
  13.           oneCount++;
  14.           sb.Append("1");
  15.         }
  16.         else
  17.         {
  18.           zCount++;
  19.           sb.Append("0");
  20.         }
  21.       }
  22.       var endSearch =2 * Math.Min(oneCount, zCount);
  23.       var maxlength = 0;
  24.       var index = 0;
  25.       for (int i = 0; i < data.Length; i++)
  26.       {
  27.         var count = 0;
  28.         for (int j = i; j < Math.Min( i + endSearch,data.Length); j++)
  29.         {
  30.           count += data[j] ? 1 : -1;
  31.           if (count == 0 &&  maxlength < j-i)
  32.           {
  33.             maxlength = j - i +1;
  34.             index = j;
  35.           }
  36.         }
  37.       }
  38.       Console.WriteLine(String.Format("{0}:{1} --> {2}",
  39.       rawdata,
  40.       sb,
  41.       maxlength));
  42.       return maxlength;
  43.     }

The test was done by just walking values and spot checking.

Code Snippet
  1. for(long i=1; i < 32; i++)
  2. {
  3.   Questions.Subsequence(i);
  4. }

Resulting in this output.
image

 

The example for 17, yielding just 2 appears to confirm correctness.

Comments

Popular posts from this blog

Yet once more into the breech (of altered programming logic)

Simple WP7 Mango App for Background Tasks, Toast, and Tiles: Code Explanation

How to convert SVG data to a Png Image file Using InkScape