geraskov
BAN USER1. Put numbers between 0 and n-1 to a[number]
2. Process array and if (a[i] != i) -> number "i" is missing
3. Put numbers between n to 2*n-1 to a[number-n]
4. Process array and if (a[i] != i + n) -> number "i + n" is missing
public class AbsentNumbers {
public static void main(String[] args) {
int[] array = new int[]{8,4,12,0,7,3,1};
printAbsentNumbers(array);
}
private static void printAbsentNumbers(int[] array) {
//sort 0 to n-1
for (int i = 0; i < array.length; i++) {
if (array[i] < array.length){
int temp = array[array[i]];
array[array[i]] = array[i];
array[i] = temp;
}
}
//check 0 to n-1
for (int i = 0; i < array.length; i++) {
if (array[i] != i){
System.out.print(i + " ");
}
}
//sort n to 2*n-1
for (int i = 0; i < array.length; i++) {
if (array[i] >= array.length){
int temp = array[array[i] - array.length];
array[array[i] - array.length] = array[i];
array[i] = temp;
}
}
//check n to 2*n-1
for (int i = 0; i < array.length; i++) {
if (array[i] != i + array.length){
System.out.print(i + array.length + " ");
}
}
}
}
According to the task we need to guess a word from the dictionary - fixed amount of words. I guess we should try to minimize calls to the Machine with our word candidate. Lets say method MatchedCharsAnswer(Word) does that: returns how many characters our Word matched with Answer. I also assume that if answer is "AA" MatchedCharsAnswer("A") and MatchedCharsAnswer("ABC") return 1 as we matched first character "A" of the Answer.
Note: for any pair of the words their matched characters are fixed and known(can be calculated by us in our method MatchedChars(word1, word2) by simply comparing characters on the same positions). Also MatchedChars(word1, word2)==MathedChars(word2, word1).
For ex. for "cat" and "pet" it is 1. MatchedChars("cat", "pet")==1 as character at position number 3 is same - "t".
How do we know the word W we just checked is the answer? According to the task Answer is one of words from the Dictionary. If MatchedCharsAnswer(W) == W.length and there is no word (W+) which starts from W in the dictionary and MatchedCharsAnswer(W)<MatchedCharsAnswer(W+). For example W="great" and W+ is "greatest".
1. Guess some random word W1 from the dictionary (or longest one): M1 = MatchedCharsAnswer(W1)
2. Check W1 is not answer
3. If word is not guessed search for the word W2 in the dictionary so that MathedChars(W1, W2)==M1 as we know that the Answer can be only among such words.
3. M2 = MatchedCharsAnswer(W2).
4. Check if W2 is the answer
5. If answer is not found, find word W3 in the dictionary so that
MathedChars(W1, W3)==M1 and
MathedChars(W2, W3)==M2
...
6. If answer is not found, find word Wx in the dictionary so that
MathedChars(W1, Wx)==M1
MathedChars(W2, Wx)==M2
MathedChars(W3, Wx)==M3
...
5. Continue till answer is found.
1. Traverse from left and get the endIndex from where numbers break increment sequence. This is our LEFT part of the array
2. Find MIN element in the right part of the array.
3. Cut LEFT part so it would have all elements <= MIN(binary search). This is SORTED_LEFT
4. Do same from right(without touching SORTED_LEFT as all smallest elements are there) and you'll have SORTED_RIGHT
5. What is left is unsorted subarray
Binary search would work better O(log n)
- geraskov January 05, 2016