Single number (is there any btr solution than this??)


  • 2
    S
    class Solution {
    public:
        int singleNumber(int A[], int n) {
            int sum=0,i;
            for(i=0;i<n;i=i+1)
            {
                sum=sum^A[i];
            }
            return sum;
        }
    };

  • 1
    M

    This is the fastest algorithm to solve this problem, with the main "optimizations" being basically cosmetic. However, since you know there is a single number, at the very least, you can do this:

    class Solution {
    public:
      int singleNumber(int A[], int n) {
        int sum = A[0], i;
        for(i=1;i<n;i++)
          sum ^= A[i];
        return sum;
      }
    }
    

    The first element is known to exist, so you can start with sum holding it instead of starting with xor of 0 and A[0]. It only saves one bitwise operation, though.


  • 0
    S

    @mike: Yeah almost similar to my code but ua saving one iteration than me :) anyways Thanq


  • 0
    M

    Sorry, by "this," I was referring to your algorithm.


  • 0
    S
    This post is deleted!

  • 0
    S

    You can use a little less space by using n rather than allocating i.

    I wouldn't use the name sum because it's misleading.

    With the one less iteration trick:

    class Solution {
    public:
        int singleNumber(int A[], int n) {
            int r = A[--n];
            while( n > 0 ) { r^=A[--n]; }
            return r;
        }
    };
    

  • 0
    S

    yeah !! Thanq


  • 0
    H

    after converting to for

    [code]
    class Solution {
    public:
    int singleNumber(int A[], int n) {
    for (int r = A[--n]; n > 0; r^=A[--n]) {}
    return r;
    }
    };
    [/code]


  • 0
    S

    @hebele: That shouldn't work. int r is in the scope of the for loop, which makes it out of scope at the return.


Log in to reply
 

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