@rajveer_90hotmail.com I just added the 4th paragraph.
douglasleer
@douglasleer
Posts made by douglasleer

RE: Sharing explanation of the solution

RE: I dont know what this message means...who can tell me ?
Consider the test case where the list has only one element, the head, and the head's next pointer points to itself, i.e, head>next = head;
Your inner while loop will never be entered, because front always equals back.
Your outer while loop will be endless because front will always be the head, which is not null.
So, you have TLE. 
Test Case Problem when n = 0
OJ's test case of n = 0 has a result of [0].
But I think the result of n = 0 should be [], i.e., an empty list, instead of a list with 0.
My argument is that, n is the number of bits. If n = 0, it means 0 bits, i.e., no bits!
What number can have not bits? Even 0 has at list one bit, which is 0.If you assume that [0] should be returned when n = 0, then, you mean 0 has no bits.
Then you need to remove 0 from [0, 1], which is the result when n = 1. This doesn't make sense.Anyone agree with me?

RE: Sharing explanation of the solution
The diff bit should be the 1 (either the first 1, or the second). If the bit of XOR is 0, it means their bits (at that location) do not differ.

RE: Just a solution.. O(nlogn) with O(n) space... Not the best..
I think this solution is even not correct. For example, 4, 5, 5, 6. Your output will be 4, 5, 5, 6. But the only correct answer is 5, 6, 4, 5.

RE: Expected output if input string contains 1 or 0
Seems the input digits will never contain 0 or 1.

Java Solution, Easy to understand and easy to implement, though kinda slow
The string may contain various symbols. I feel it's not that clear to solve the problem within one pass.
My logic is simple:
Partition the string according to the position of 'e'. If 'e' is not found, then, the entire string must be a floating point number without 'e' for it to be valid.
If 'e' is found, then, the part of string before the 'e' must be a floating point number without 'e', and the part of the string after 'e' must be an integer (signed or unsigned).
It's easy to determine whether a string is an integer.
To check whether a string is a floating point number without 'e', I first remove a possible sign at the beginning of it. Then, I adopt a similar approach: partition the string according to '.'. If '.' is not found, then the string must be an unsigned integer for it to be valid. If '.' is found, the the part of the string before '.' (s1), and the part of the string after '.' (s2) must satisfy the following conditions for the string to be valid:
 if (s1.length() == 0), s2 must be a valid unsigned integer.
 if (s2.length() == 0), s1 must be a valid unsigned integer.
 if both of them are not empty, both of them must be unsigned
integers.
It's slow, because we need to traverse the string multiple times.
public class Solution { public boolean isNumber(String s) { s = s.trim(); if (s.length() == 0) return false; int i = 0; int ePos = 1; // position of an 'e' in the string. while (i < s.length()) { if (s.charAt(i) == 'e') { ePos = i; break; } ++i; } if (ePos == 1) return isFloating(s); else return isFloating(s.substring(0, ePos)) && isInteger(s.substring(ePos + 1)); } private boolean isFloating(String s) { if (s.length() == 0) return false; int dotPos = 1; // position of an '.' in the string. int i = 0; // need to remove the symbol first. if (s.charAt(i) == '+'  s.charAt(i) == '') ++i; int start = i; while (i < s.length()) { if (s.charAt(i) == '.') { dotPos = i; break; } ++i; } if (dotPos == 1) return isUnsignedInteger(s.substring(start)); else { if (start == dotPos) return isUnsignedInteger(s.substring(dotPos + 1)); else if (dotPos == s.length()  1) return isUnsignedInteger(s.substring(start, dotPos)); else { return isUnsignedInteger(s.substring(start, dotPos)) && isUnsignedInteger(s.substring(dotPos + 1)); } } } private boolean isInteger(String s) { if (s.length() == 0) return false; int i = 0; if (s.charAt(i) == '+'  s.charAt(i) == '') ++i; return isUnsignedInteger(s.substring(i)); } private boolean isUnsignedInteger(String s) { if (s.length() == 0) return false; for (int i = 0; i < s.length(); ++i) { if (!Character.isDigit(s.charAt(i))) return false; } return true; }
}

RE: C++ Quad tree (736ms ) and indexed tree (492ms) based solutions
Thanks! I also give you an upvote. You've done a great job on implementing them. I've been searching for 2D segment tree for days. The only detailed source that seems to be correct is http://emaxx.ru/algo/segment_tree.
However, the website is in Russian. And I haven't fully understand all the ideas and implementations. Do you have any shareable information on 2D Segment tree? 
RE: C++ Quad tree (736ms ) and indexed tree (492ms) based solutions
The time complexity for 1D segment tree does not extend to QuadTree. For instance, consider a 2^n x 2^n grid. If you query the rectangle (0, 0)  (2^n  1, 0), or any singlerow slice, you end up having to look at 2^n different 1x1 squares. Thus, the time complexity for QuadTree is linear, O(max(n, m)).
The time complexity of O(max(n, m)) is greater than O(logn * logm). Thus, 2d segment tree is more efficient.

RE: Is a log(n) solution?
The time complexity of a 2D segment tree (instead of a quadtree) should be O(logn * logm).