7
\$\begingroup\$

The question is to find the sum of Digit XOR till \$N\$.

For eg:- Digit XOR of a number 112

112 => 1 xor 1 xor 2 = 2

So we need to find

int digit_xor_sum=0
for(i=1;i<=N;i++){
  digit_xor_sum+= digit_xor(i);
}
return digit_xor_sum

My Solution Approach was as follows,

 int digit_xor(int n){
    if(n<=9){
        return n; // because there is only 1 digit
    }

    int digit_xor_sol=(n%10); // intialising digit_xor_sol with last digit
    n/=10; // removing the last digit

    while(n){
        digit_xor_sol = digit_xor_sol ^ (n%10);  // xor the current last digit and current xor solution
        n/=10;
    }

    return digit_xor_sol;
}

But this is \$O(nlogn)\$, which is time expensive.

Then I found a better solution like the below, which takes \$O(n)\$:

int digit_xor[1000];

int find_digit_xor(int n){
    if(n<=9)
        return digit_xor[n]=n;

    if(digit_xor[n]!=-1){ // there are multiple test-cases, so no need to recompute again
       return digit_xor[n];
    }
    return digit_xor[n] = digit_xor[n/10]^(n%10);
}

int main(){

 int sum;
 memset(digit_xor,-1,sizeof digit_xor);

 int testcase;
 scanf("%d",&testcase);

 while(testcase--){
     int n;
     scanf("%d",&n);

     sum=0;

     for(int i=0;i<=n;i++)
         sum+=find_digit_xor(i);

     printf("%d\n",sum);
 }
 return 0;
}

But this too is time expensive for larger \$N\$.

Is there any direct formula to calculate this SUM in \$O(1)\$.

\$\endgroup\$
1
  • \$\begingroup\$ digit as in decimal representation? In binary, it is parity. Over at stackoverflow, there must be several questions regarding the "cumulative ExOr" of binary representations. (I'd be surprised if it was impossible to derive a closed formula.) \$\endgroup\$ – greybeard Dec 21 '16 at 9:13
4
\$\begingroup\$

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 <stdio.h>
#include <stdint.h>
#include <string.h>
#include <stdbool.h>

#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<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 < k)
        k = n-k;

    for (i=0;i<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<i;j++)
        waysPerCombo *= numInSet;
    for (j=i;j<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 <= 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<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 > 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", &numTests);
    while (numTests--) {
        uint64_t n;

        scanf("%lld", &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 <= 9; digit++) {
        int count = 0;
        for (int place = 0; place <= maxDecimalPlace; place++) {
            count += GetCount(n, digit, place);
        }
        if (count & 1)
            totalXor ^= digit;
    }
    return totalXor;
}

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

\$\endgroup\$
3
  • \$\begingroup\$ I think you've made the same mistake that I did: the required result isn't the xor of all of the digits in the integer, but the integer sum over the numbers of the xor sum of their digits. \$\endgroup\$ – Peter Taylor Dec 21 '16 at 11:58
  • \$\begingroup\$ @PeterTaylor Yes I seem to have misread the question. I agree with your answer where you need to find the count of numbers that contain an odd number of digits for each of the four bits: 0x1, 0x2, 0x4, and 0x8. \$\endgroup\$ – JS1 Dec 21 '16 at 20:09
  • \$\begingroup\$ @PeterTaylor You might be interested in my implementation of the solution you suggested. \$\endgroup\$ – JS1 Dec 22 '16 at 7:01
3
\$\begingroup\$

The better solution should take \$O(N)\$, but it has a bug:

int find_digit_xor(int n){
    if(n<=9)
        return digit_xor[n]=n;

    if(digit_xor[n]!=-1){ // there are multiple test-cases, so no need to recompute again
        digit_xor[n];

That line is missing a return, so it never exploits the cache.


It is possible to calculate it in \$O(\lg N)\$ time, but it's a bit complicated.

Consider how to count numbers \$1 \le i \le N\$ such that digit_xor(i) & 1 == 1. That requires an odd number of digits d such that d & 1 == 1. The valid digits are \$D_1 = \{1, 3, 5, 7, 9\}\$.

Let \$c(n, D)\$ be the number of n-digit numbers (including those with leading zeroes) with an odd number of digits from the set \$D\$. Then the number of n-digit numbers with an even number of digits from the set \$D\$ is \$10^n - c(n, D)\$. Now, clearly \$c(1, D) = |D|\$; and $$\begin{eqnarray}c(n + 1, D) & = & (10 - |D|)c(n, D) + |D|(10^n - c(n, D)) \\ & = & (10 - 2|D|)c(n, D) + 10^n |D| \end{eqnarray}$$ which has closed form $$c(n, D) = \frac{10^n - (10 - 2|D|)^n}{2}$$

So how many numbers do we have with digit_xor(i) & 1 == 1? If \$N\$ has \$n\$ digits, it's \$c(n-1, D_1)\$ plus those between \$10^n\$ and \$N\$. Those can be separated into the ones with the same first digit as \$N\$ and those with a smaller first digit; the latter can be handled easily, and the former require a recursion.

Once you've got that implemented, it should be easy to generalise it to handle sets \$D_2 = \{2, 3, 6, 7\}\$, \$D_4 = \{4, 5, 6, 7\}\$, and \$D_8 = \{8, 9\}\$.

Finally you weight the four counts by the corresponding value of the bit and add them.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.