Qestion

• input: an integer array with 1 or 0 for each index
• output: last character is double or single character
• 0XXXXXXX: Single character
• 1XXXXXXX XXXXXXX: Double character

Algorithm

• split the input by 8 length
• check the first bit of last byte
  • if it is 1, then the last character is double
  • otherwise, traverse from last slice to first slice and count the number of 1 at first bit in each slice until the first bit is 0
    • if the number of 1 is even, the last character is single
    • otherwise, the last character is double

Code

public String doubleOrSingLastChar(int[] input) {
       int len = 8;
       int i = input.length - 8;
       if (input[i] == 1) {
           return "Double";
       }
       i -= len;
       int count = 0;
       while (i >= 0 && input[i] == 1) {
           count++;
           i -= len;
       }
       if (count % 2 == 1) {
           return "Double";
       } else {
           return "Single";
       }
   }

Complexity

• time complexity: O(N)
• space complexity: O(1)