arun.edarath
BAN USER1) First we need to store the index of all unique characters in an array of fixed size.
2) Now find the smallest index from this array.
Here is the code
int find_first_unique_index()
{
int index, small_idx = INT_MAX, temp;
char array[256], c;
for (index = 0; index < 256; index++) {
array[index] = 0;
}
index = 1;
while (hasNextChar()) {
c = getNextChar();
if (array[c] > 0) {
/* Invalidate the index */
array[c] = -array[c];
} else if (array[c] == 0) {
array[c] = index;
}
index++;
}
/* Now find the smallest valid index */
for (index = 0; index < 256; index++) {
temp = array[index];
if (temp > 0 && temp < small_idx)
small_idx = temp;
}
return small_idx;
}
Here is the code.
This is how it works
1) Iterate till the end of unique character window, saving the index of each char in array.
Lets say unique window starts at "x" and stops at "y"
and character at index "z" is repeated at "y" + 1
2) Reset the index in array for characters from "x" to "z" including "z"
3) Again start the procedure from "y". Note that we don't reset the indices for characters between "z" and "y" as we already know they are unique
int find_longest_unique_str(char *str)
{
int array[256], i, size, index, temp_size;
char *fast, *start, *slow, c, *temp, *dup;
for (i = 0; i < 256; i++)
array[i] = -1;
slow = start = str;
size = temp_size = index = 0;
while (*slow) {
fast = slow;
while (*fast) {
c = *fast;
if (array[c] == -1)
/* store the index */
array[c] = fast - str;
else
break;
fast++;
}
temp_size = fast - start;
if (temp_size > size) {
size = temp_size;
index = start - str;
}
/* pointer to duplicate char */
dup = str + array[c];
/* Reset values from "start" to "dup" including dup */
for (temp = start; temp <= dup; temp++) {
c = *temp;
array[c] = -1;
}
/* Again start from where we stopped; now we know that
* the characters between 'dup' and 'fast' are unique */
slow = fast;
start = dup + 1;
}
printf("size of longest unique string = %d\n", size);
return index;
}
code for removing duplicates in just one pass assuming that input contains only
small letters of English alphabet.
Time complexity = O(n) ; space complexity = O(1).
int remove_dup(char *str)
{
int c, i = 0;
/* Assuming all small letters */
char *temp = str, array[26];
for (i = 0; i < 26; i++)
array[i] = 0;
i = 0;
while (*temp) {
c = *temp++;
if (array[c - 'a'] == 0) {
array[c - 'a'] += 1;
str[i++] = c;
}
}
str[i] = 0;
/* Return new size */
return i;
}
Code for finding the max value in O(logn) assuming the increasing and decreasing part don't have duplicates.
int find_max(int *array, int size)
{
int low_bound, mid, low, high;
low_bound = low = 0;
high = size - 1;
while (low <= high) {
mid = (low + high) / 2;
if (mid == low_bound) {
/* Only one element */
if (mid == high)
return mid;
else
/* 2 elements in increasing order */
return mid + 1;
}
if (array[mid - 1] < array[mid] && array[mid] < array[mid + 1])
low = mid + 1;
else if (array[mid - 1] > array[mid] && array[mid] > array[mid + 1])
high = mid - 1;
else /* max value found */
return mid;
}
}
Add "1" only when both end with a bit 1 (aka both are odd)
int computeAvg(int a, int b)
{
return (a >> 1 + b >> 1 + (a&b) &1);
}
Repstephenroach41, Android Engineer at Alliance Global Servies
Experienced and professional facilities coordinator with a commitment to customer service. An analytical business person as well as a practiced ...
I think it can be acheived with complexity equal to the size of denominations. Here is the code
- arun.edarath November 24, 2012