Impossible to solve without extra space. Always need space for constants, variables or whatever. Recursion calls will take space for call stack.
If you are talking about constant space, then even declaring a string / stack will take constant space. (In fact at most (log(10, INT_MAX) * sizeof char), which is no worse than declaring an integer or more). Actually, even recursion will take constant space.
I think by extra-space they meant not you can use space constant space but not linear or quadratic space.
When you call a function, you use stack space to save return address and allocate necessary context, I think this problem cannot be solved, at least cannot be solved by computer.
Linear or quadratic in what? Allocating a
char is constant, and it's the upper bound of log10 N, where N is the input number. Not even linear.
Agreed. The spoiler says we can't make it a string because of the no-extra space requirement.
If a string, which represents an integer (apparently constant space), is not allowed, then all the answers that use an integer to hold the reverse of the integer (or half digits of the integer) also won't work.
There are so many questions in LeetCode that require people don't use extra space. If you think this is meanless, then I have to say LeetCode is meanless. Speaking is not coding, you can't still be strick when you speaking or listening.
Also I am wondering why so many people like this post.
@Harrywithcode Many questions ask for O(1) space, not for no space. And those questions have some meaningful problem size, so that solutions can be O(N^2) space, O(N) space, O(lg N) space and so on. In this problem, you obviously need some extra space, and it will obviously be O(1) space, assuming integers are of fixed size. So unless you count some really crazy solutions (and you don't count constants as extra space), the problem description makes no sense. It would probably be much better to say something like “don't convert to string, and don't use arrays”.
came up with a solution without extra 'variable' though
I have been thinking for a whole day how to solve this problem in-place, for me don't use extra space meant don't use any variables and I thought I was dumb.
I did it!
My solution without any extra space:
Also this problem is 100% incorrect. It asks for the palindrome of an integer when what it is really asking for the palindrome of a string.
diao zhan tian (yao xiao si le)
@yuki_shan ha ha ha~
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.