Find the Sum of Digit XOR till N?
Updated review

Peter Taylor noticed that I was solving for the wrong problem.  The problem calls for a sum of xor sums, not a single xor sum.  So I'm updating a review to talk about the actual problem (the old review is at the end, for reference).

Current solution is \$O(n)\$, is it enough?

The current solution with memoization runs in \$O(n)\$ time.  I was able to run with n = 200000000 (200 million) in under one second.  The question did not specify how many test cases there would be and how large \$n\$ could be for each testcase.  But since the OP said it wasn't fast enough, I'm going to assume that \$n\$ could be very large.  In that case, both time and space become a concern.

Can be solved in \$O(\log n)\$ time and space

Peter Taylor's answer outlined a solution where you solve for each of four bits (1,2,4,8) separately and then add up to a final total.  This solution requires \$O(\log n)\$ time due to its recursive nature, but does not use any extra space other than the \$O(\log n)\$ space needed to handle the recursion.

I got interested in how difficult it would be to implement this solution, so I did it.  I also tested versus the memoized version to make sure it worked.  Here is the result (quite long due to the number of comments):

#include &lt;stdio.h&gt;
#include &lt;stdint.h&gt;
#include &lt;string.h&gt;
#include &lt;stdbool.h&gt;

#define MAX_DIGITS        20

const uint8_t ones[]   = { 1, 3, 5, 7, 9 };
const uint8_t twos[]   = { 2, 3, 6, 7 };
const uint8_t fours[]  = { 4, 5, 6, 7 };
const uint8_t eights[] = { 8, 9 };

// Returns true if "digit" is in the given set of digits "digitSet".
// For example, 3 is in the set { 1, 3, 5, 7, 9 }.
static bool isInSet(int digit, const uint8_t *digitSet, int numDigitSet)
{
    int i = 0;

    for (i=0;i&lt;numDigitSet;i++) {
        if (digitSet[i] == digit)
            return 1;
    }
    return 0;
}

// Returns (n choose k), which is the number of ways to choose k objects from
// a set of n objects.
static uint64_t combinations(int n, int k)
{
    int      i   = 0;
    uint64_t ret = 1;

    // nCk equals nC(n-k), so solve for the easier case.
    if (n-k &lt; k)
        k = n-k;

    for (i=0;i&lt;k;i++) {
        ret *= (n-i);
        ret /= (i+1);
    }
    return ret;
}

// Given every possible number of numDigits length, return the number of ways
// that you can make a number with an odd/even number of digits coming from
// a set of size numInSet.  For example:
//
// 5 digits
// 4 numbers in the set
// odd
//
// Let D be a digit in the set and x be a digit not in the set.
//
// Since we are considering only odd possibilities, we can make numbers with
// either 1 D, 3 Ds, or 5 Ds, like this:
//
// Dxxxx xDxxx xxDxx xxxDx xxxxD = 1 D  (5 choose 1 =  5 ways to place)
// DDDxx DDxDx DDxxD DxDDx etc.  = 3 Ds (5 choose 3 = 10 ways to place)
// DDDDD                         = 5 Ds (5 choose 5 =  1 way  to place)
//
// Within each of the ways above, such as Dxxxx, there are also many ways
// to build the digits.  There are numInSet digits (4 in the example) that
// can be put in each D slot, and (10 - numInSet) digits (6 in the example)
// ways to fill each x slot.  So for Dxxxx, there are 4*6*6*6*6 ways to create
// a matching number of that pattern.  For DDDxx, there are 4*4*4*6*6 ways.
// For DDDDD there are 4*4*4*4*4 ways.
//
// So the answer for the example above would be:
//
// 5*(4*6*6*6*6) + 10*(4*4*4*6*6) + 1*(4*4*4*4*4) = 49984 ways
//
static uint64_t computeCount(int numDigits, int numInSet, bool odd)
{
    int      i            = (odd ? 1 : 0);
    int      j            = 0;
    uint64_t ret          = 0;
    int      numNotInSet  = 10 - numInSet;
    uint64_t waysPerCombo = 1;

    // Special case for 0 digits.
    if (numDigits == 0)
        return odd ? 0 : 1;

    // Preinitialize waysPerCombo so we don't have to recompute the whole
    // thing every time through the next loop.  We will only need to adjust
    // it for 2 digits every loop iteration.  This is the 4*6*6*6*6 factor
    // from the example above.
    for (j=0;j&lt;i;j++)
        waysPerCombo *= numInSet;
    for (j=i;j&lt;numDigits;j++)
        waysPerCombo *= numNotInSet;

    // Loop through each possible way to make an odd/even number of digits
    // up to numDigits (such as 1, 3, 5 in the example above).  For each
    // number of digits, there are (numDigits choose i) possible ways to
    // make a Dxxxx pattern, and waysPerCombo ways of filling that pattern
    // with digits.
    for (; i &lt;= numDigits; i += 2) {
        ret += combinations(numDigits, i) * waysPerCombo;
        waysPerCombo /= numNotInSet * numNotInSet;
        waysPerCombo *= numInSet * numInSet;
    }
    return ret;
}

// This function computes the "digit xor sum" for the specified number and
// "bit" (either 1, 2, 4, or 8).  This bit is specified by the digit set that
// is passed in.  The number is given as an array of digits, with the least
// significant digit in digits[0].  For example, the number 573 would be
// passed in as the array { 3, 7, 5 }.
//
// digits   : An array of digits for a given number, with the least significant
//            digit in digits[0].  For example, if the number was 573, then the
//            digit array would be { 3, 7, 5 }.
// numDigits: The length of the digits array.
// digitSet : The set of digits we are solving for (e.g. ones, twos).
// numDigitSet: The length of the digitSet array.
// odd:       True if we are looking for an odd number of occurrences of the
//            specified bit.  False if we are looking for an even number.
static uint64_t computeXorSumForBit(int *digits, int numDigits,
                const uint8_t *digitSet, int numDigitSet, bool odd)
{
    int      i            = 0;
    int      leadingDigit = digits[numDigits-1];
    uint64_t sum          = 0;
    bool     findOdd      = false;

    // Special case for 0 digits.
    if (numDigits == 0)
        return odd ? 0 : 1;

    // For each digit leading up to the leading digit, we can use all of the
    // other digits.  For example, given the number 521, we can use all of
    // 0xx 1xx 2xx 3xx 4xx, but we can't use all of 5xx, only up to 521.
    //
    // If the digit we use is part of the set, then we need to flip the odd
    // variable because we are using 1 of that digit already.
    for (i=0; i&lt;leadingDigit; i++) {
        findOdd = odd ^ isInSet(i, digitSet, numDigitSet);
        sum += computeCount(numDigits - 1, numDigitSet, findOdd);
    }

    // For the leading digit (5 in the 521 example), we are limited by the
    // other digits.  We can recurse into this same function, and solve for
    // one fewer digit.  For example, with 521, we solve for 21, and flip
    // the odd variable if 5 is part of the set.
    findOdd = odd ^ isInSet(leadingDigit, digitSet, numDigitSet);
    sum += computeXorSumForBit(digits, numDigits-1, digitSet, numDigitSet,
                findOdd);

    return sum;
}

// Computes the sum of "xor of digits" for all numbers from 1..n.  The xor of
// digits is the xor of each digit (base 10) in a number.  For example, if the
// number was 521, the xor of digits is 5 ^ 2 ^ 1 = 6.
//
// The method used here is to solve for each of the four bits (1, 2, 4, 8)
// separately.  For a particular bit such as 1, we count how many numbers
// between 1 and n have an odd number of digits containing the 1 bit (i.e.
// an odd number of these digits: 1,3,5,7,9).  These numbers will have an
// xor of digits value with 0x1 set.  All other numbers will have an xor
// of digits value with 0x1 clear.
static uint64_t computeXorSum(uint64_t n)
{
    uint64_t sum       = 0;
    int      numDigits = 0;
    int      digits[MAX_DIGITS] = {0};

    while (n &gt; 0) {
        digits[numDigits++] = n % 10;
        n /= 10;
    }

    sum +=   computeXorSumForBit(digits, numDigits, ones,  sizeof(ones), true);
    sum += 2*computeXorSumForBit(digits, numDigits, twos,  sizeof(twos), true);
    sum += 4*computeXorSumForBit(digits, numDigits, fours, sizeof(fours), true);
    sum += 8*computeXorSumForBit(digits, numDigits, eights,sizeof(eights),true);

    return sum;
}

int main(void)
{
    uint64_t sum      = 0;
    int      numTests = 0;

    scanf("%d", &amp;numTests);
    while (numTests--) {
        uint64_t n;

        scanf("%lld", &amp;n);
        sum += computeXorSum(n);
    }
    printf("%lld\n", sum);
    return 0;
}


Old review (solves a different problem)

I don't know about \$O(1)\$ but it seems doable in \$O(\log n)\$.  Given a number \$n\$, you can compute how many times each digit appears in each decimal place.  For example, given the number 1000, I can tell you the digit 1 appears 1 time in the thousands digit, 100 times in the hundreds digit, 100 times in the tens digit, and 100 times in the ones digit, for a total of 301 times.

If you xor a digit an even number of times, you get 0.  If you xor a digit an odd number of times, you get the digit.  So in my example, you xor the digit 1 an odd number of times (301 times) and get 1.  Then you solve for digits 2..9 and xor all the digit results together.

Now the question is, how did I compute the count of the digit 1 in each decimal place?  I suggest you start with the ones place (the rightmost digit) and think about why the answer for any digit is always N/10 or N/10 + 1.  Then think about the tens place and think about why the answer is always between N/10 - (digit-1) and N/10 + (10-digit).  Once you figure out the pattern, you should be able to write a function like this:

int GetCount(int n, int digit, int decimalPlace);


Then your main computation would look like:

int ComputeDigitXor(int n)
{
    int totalXor = 0;
    int maxDecimalPlace = ComputeMaxDecimalPlace(n);
    for (int digit = 1; digit &lt;= 9; digit++) {
        int count = 0;
        for (int place = 0; place &lt;= maxDecimalPlace; place++) {
            count += GetCount(n, digit, place);
        }
        if (count &amp; 1)
            totalXor ^= digit;
    }
    return totalXor;
}


I'll leave it up to the reader to figure out how to write GetCount() given the hints above.