The sum of the special function in the range

Question

I want to calculate the sum of a function defined over [L, R].

The function first computes the xor of each substring of the number, and then adds various values ​​and returns them.

Eg: F(312) 
    3 = 3
    3^1 = 2
    3^1^2 = 0
    1 = 1
    1^2 = 3
    2 = 2
    Sum of distinct values = 3+2+1 = 6 = F(312)

How can I calculate this quickly? L, R may range from 1 to 1,000,000,000.

For example: if I give L = 5 and R = 15, then the function should calculate F (5) + F (6) + F (7) ... + F (15)

Answer 1

One possible solution in JavaScript might look like this:

<script type="text/javascript">

function sumXorSubStr(numStr)
{
  numStr = parseInt(numStr).toString();

  var
    results = {},
    lastPos = numStr.length -1
  ;

  for(var start=0 ; start <= lastPos ; start++)
    for(var op = 0, i = start ; i <= lastPos ; i++)
      results[ op ^= numStr[i] ] = 1;

  var sum = 0;
  for(var i in results)
    sum += parseInt(i);
  return sum;
}

alert( sumXorSubStr(312) );

</script>

The wrapper function for an I / O loop is a non-optimal way. More performance can be achieved by combining it into one function.

function sumRangeXorSubStr(from, to)
{
  var result = 0;

  for(var n=from; n<=to; n++)
    result += sumXorSubStr(n);

  return result;
}

, , ...