Michael
BAN USERThis problem is solvable in O(N) runtime without a stack or queue in C or C++. Here I use manipulation of the first pointer so that each recursive call advances the last pointer and the first pointer simultaneously.
bool isPalindrome(node* head) {
return checkPalindrone(*head, head);
}
bool checkPalindrome(node** first, node* last) {
// If last is not the last node then advance last pointer, which
// also advances first pointer every time a boolean is returned
if (last->next) {
node* next_node = last->next;
if (next_node->next) {
next_node = next_node->next;
}
// Advances first pointer and checks if this is part of palindrome
if (!checkPalindrome(first, next_node) {
return false;
}
}
// Base case is when first and last are same or adjacent, at which point
// we stop advancing first pointer and check if first and last are equal
if (*first == last) {
return true;
} else if (*first->next == last) {
return *first->data == last->data;
}
// Otherwise check if last and first have same data, then move first node
if (*first->data == last->data) {
*first = *first->next;
return true;
}
return false;
}
Actually the hasNext() function does not increment the union iterator. It instantiates a new iterator from the collection of iterators, which does not have shared state because it advances over the collection. However the union iterator's next() function will not work because it instantiates a new iterator over the collection each time it is called, which will result in it always removing the next element from the first iterator with another element. Instead this iterator should be a member variable so that the union iterator can track the current iterator in the collection and get the next element from the next iterator.
- Michael May 02, 2015Your formula appears incorrect for total occurrences of a single digit within all possible numbers with n digits. Assuming the digit is 1-9 it should be 1+9*1+9*10*1+...+9*10^(n-2)*1=1+9*sum(i=0,...,n-2 : 10^i)=1+9*(1-10^(n-1))/(1-10)=1+(10^(n-1)-1)=10^(n-1) if we count each digit location individually.
- Michael January 18, 2015I was thinking along the same lines until the following counterexample. If the numbers are arranged as follows then it becomes impossible to fill the lower fourth square because both 4 and 1 must go in the lower right, which is clearly impossible.
| 1 2 | 4 3 |
| 3 4 | 1 2 |
------------ |
| 4 1 | * * |
| * * | * * |
This means we have to somehow take into account that after filling in the left top square, the top right square cannot have column with the same numbers as any row of the lower left square.
Also the following board should be impossible.
| 1 2 | 3 4 |
| 3 4 | 2 1 |
------------ |
| * * | * * |
| 4 1| * * |
In both of these cases it looks like there are two ways to fill in the lower left square rather than four, so this means that the total number of solutions should be 4!*2*4 + 4!*2*2 = 4!*2*6 = 288 instead of 384.
This solution has runtime O(4^N) for N buildings and there must be a more optimal way to do this, but right now I can't think of a better solution other than brute force.
- Michael May 18, 2015