ftfish
BAN USERYes.
There're some O(nlogn) algorithms which can solve the 2D closest points problem. Reducing the problem to 1D gives the answer.
Note that if this problem can be solved under O(nlogn) time, the classical element uniqueness problem can also be solved under O(nlogn) time, which contradicts the known lower bound of that problem.
But, when randomized algorithms and something like hashtable are allowed, it is also possible to solve this in O(n) expected time. google helps if you want to know more.
A solution to Euler or Hamilton can be used to solve the original problem.
But not all instances of Hamilton can be mapped to an instance of the original problem.
For example, consider a directed (Hamiltonian) graph with 4 nodes 1..4. The edges are:
1->2
2->1
2->3
3->2
1->4
4->3
If node 1 is a string starting with x and ending with y (denoted simply as xy), the edges 1->2 and 2->1 make sure that node 2 must be yx. Similarly node 3 must be xy.
What now?
Node 4 must start with y because there's an edge 1->4.
On the other hand it must end with x because edge 4->3 exists. So node 4 must be yx. But there's no edge 4->1 and 3->4, which must exist!
There're only 7 2digit numbers with sum of digits 8. It's easy to find 35 is the solution.
A more mathematical solution:
Let the last digit of the number be d.
so ((8-d)*10+d)+18 = d*10+(8-d)
This gives the answer d = 5 and then the number is 35.
An easier mathematical solution:
d+8 == 8-d (mod 10)
=>
2d == 0 (mod 10)
the only solution in 1..8 is d=5.
maintain a hash table of characters in the window (including the number of appearances) and a global counter indicating how many chars in the set T are in hashtable.
left border i moves right => remove one character s[i] (number of appearances--) from the hashtable. If the count of s[i] becomes 0, decrement the global counter.
right border j moves right => insert one character s[j] into the hashtable. if s[j] is in T and s[j] was not in the hashtable, increment the global counter.
move the left border by one every time, and move the right border right (possibly stays still) until the global counter == |T|
The set T should also be implemented with a hash table so that we can check whether a char is in T or not. if the chars are all in ascii, an array of size 128 will do.
No. formally (and still not completely formal) I said, when left border moves right, the right border will never move left.
In your example:
first [1,6]
The left border moves until index 5 without moving The right border. This will find [5,6].
Then another move of the left border forces the right border to move, to the end. [5,8] will not be found by my algorithm because it is clearly bigger than [5,6]
I just want to make sure that the problem is not meaningless.
- ftfish July 17, 2010E.g. if divisions are allowed, it's possible to do better than the trivial O(logn) divide-and-conquer solution.