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)
