The truly O(1) space solutions


  • -4
    P

    Many people have the O(n) space solutions, but it does not fulfill the problem request.

    This time I'll show you a truly O(1) space solution by Java and Python

    The key point is XOR arithmetic and the order of the number in the list.By using the XOR you can promise the values in pair exist. And if you add the order(location) to the XOR arithmetic then you can promise the order of the number

    Because (for every number a,b) a = a XOR b XOR b. But it can't promise their order.Just like this [1 3 2 3 2 1].So I add the sequence number to "b" to promise their order. As you can see in the code, the value "count" is the seq num and the "m" is the corresponding right one. In this way I can have an intuitive feeling to solve the problem.

    But I really know the idea is not perfect because of the function is too easy. So it just a master of time to complete the algorithm.

    //Particularly explain!

    Because the algorithm likes an encryption process. So if you want to construct 2 pairs to decrypt it, of course you can. But it just depends on the encryption function, and here I let the f(x) = x * loc(x). Then you can design a proper f(x) to make up.But this idea(encrypt) is right. Do you think so?

    Python Code

    class Solution:
        # @param {ListNode} head
        # @return {boolean}
        def isPalindrome(self, head):
            count = 0
            node = head
            while head is not None:
                count = count + 1
                head = head.next
    
            n = count
            mid = int(n//2)
            isOdd =False
            if n < 2:
                return True
    
            if n % 2 != 0:
                mid = mid + 1
                isOdd = True
    
            count = 0
            flag = 0
            while node is not None:
                count = count + 1
                if (isOdd and count == mid):
                    node = node.next
                    continue
                if count > mid:
                    m = n - count + 1
                    flag = flag ^ (node.val * m)
                else:
                    flag = flag ^ (node.val * count)
                node = node.next
            if flag == 0:
                return True
            else:
                return False
    

    Java Code

    public class Solution {
        public boolean isPalindrome(ListNode head) {
            int count = 0, flag = 0;
            ListNode node = head;
            while (head != null){
                count++;
                head = head.next;
            }
            int n = count, mid = n / 2;
            Boolean isOdd = false;
            if (n < 2) return true;
            if (n % 2 != 0){
                mid++;
                isOdd = true;
            }
            count = 0;
            while (node != null){
                count++;
                if (isOdd && count == mid){
                    node = node.next;
                    continue;
                }
                if (count > mid){
                    int m = n - count + 1;
                    flag = flag ^ (node.val * m);
                }else{
                    flag = flag ^ (node.val * count);
                }
                node = node.next;
            }
            if (flag == 0){
                return true;
            }else{
                return false;
            }
            
        }
    }

  • 2
    F

    "Of course, a sort of math knowledge is necessary if you want to understand the algorithm"

    Yeah. But apparently you don't have enough math knowledge to prove your own algorithm wrong.

    Here is a counter example:

    The list: 1->6->4->2->3->1

    According to your algorithm, it would be treated as palindrome since (1 * 1) ^ (6 * 2) ^ (4 * 3) ^ (2 * 3) ^ (3 * 2) ^ (1 * 1) = 0. But of course it is not a palindrome.


  • 0
    P

    Yes, you are right. Because the algorithm likes an encryption process. So if you want to construct 2 pairs to decrypt it, of course you can. But it just depends on the encryption function, and here I let the f(x) = x * loc(x). Then you can design a proper f(x) to make up.But this idea(encrypt) is right. Do you agree with me?


  • 0
    F

    In theory, yes. But not really in practice. How could you find a hash function that has no conflict at all? The idea is interesting though.


  • 0
    P

    Yes, as RSA, SHA-1 can be decrypted. But we still use them, because it works. And it costs more than you get. So in my opinion, I can accept the solution, at least the train of thought. compared to the O(n) space solution.


  • 0
    F

    Just for the sake of this question, you can meet the O(1) space requirement by first reversing the first half of the list, doing the palindrome checking and then reserving it back to the original, although I really found it awkward.


  • 0
    S

    well, I don't think the solution makes sense because there is already an counter test case as listed above. I would be surprised if you can accept the solution, do we accept the solution just because it works? Of course NOT, we accept the solution because it can solve almost all functional and BOUNDARY cases.

    BTW, please today people are doing more than just applying RSA/SHA-1 for better security, people are improving the algorithm (e.g SHA-2) and complexing the system, it’s a trade off between complexity and accuracy/security, so in your case, maybe you are looking for a fast delivery but not a high quality one


  • 0
    S

    Btw, it's appreciating that people pointed out a counter example, I would suggest you thank to the person


  • 0
    P

    Thanks for your comment.I think I have explained clearly my opinion. You can say this solution is not perfect.But you don't have to deny the whole work. Actually I just supply a new way to handle the problem. And if I have time I'll update a new function to fit the example.


  • 0
    S

    The solution doesn't even work for a simple boundary case, do you call it not perfect ?Actually I like you idea of XOR val * pos, that could be a smart choice for some other question, but definitely not this one. If you like to keep arguing for your incorrect solution as imperfect one ~ well, up to you. no comment any more


  • 0
    P

    Let me show you why I say it's not perfect. Then I'll add this in the solution explain.
    At first, I can promise in the list all values are in pair exist by using XOR. Because (for every number a,b) a = a XOR b XOR b. But it can't promise their order.Just like this [1 3 2 3 2 1]
    So I add the sequence number to "b" to promise their order. As you can see in the code, the value "count" is the seq num and the "m" is the corresponding right one.
    In this way I can have an intuitive feeling to solve the problem.
    But I really know the idea is not perfect because of the function is too easy.
    So it just a master of time to complete the algorithm. I pray that you understand me.


  • 0
    S

    thanks, I do understand your intention and solution, intuitive feeling is good, but we should always be capable to prove its correctness. in my opinion, we should always have a bar to guard the correctness, incorrect != imperfect. I pray that you are with me


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.