Intereting Posts

How to solve $ 13x \equiv 1 ~ (\text{mod} ~ 17) $?
Demystifying modular forms
$\angle ABD=38°, \angle DBC=46°, \angle BCA=22°, \angle ACD=48°,$ then find $\angle BDA$
How many distinct factors of $n$ are less than $x$?
Creating a function incrementally
What is the of $\lim_{x\to 0} \sin x \circ \cos x \circ \sin x \circ \cos x \dots$?
A fundamental solution for the Laplacian from a fundamental solution for the heat equation
Why do engineers use the Z-transform and mathematicians use generating functions?
Degree 1 maps from $\mathbb S^n$
Why do these equivalent categories seem to behave differently?
How to solve CSC = sin-1?
Prove $\displaystyle \int_{0}^{\pi/2} \ln \left(x^{2} + (\ln\cos x)^2 \right) \, dx=\pi\ln\ln2 $
Arranging people in a row
Group actions and associated bundles
Prove there is no contraction mapping from compact metric space onto itself

Say I have n positive numbers `A1,A2...An`

and `Ak`

is minimum among them. And `d`

is a number such that `(A1-d) ⊕ (A2-d) ⊕ .......(An-1-d) ⊕ (An-d) = 0`

where`0<=d <= Ak`

.

I want to know how many d are there . I know I can iterate all possible value of d and take XOR of n number every time and find out but complexity in this case is O(Ak∗n) which is O(n2) in worst case.

Is their any property of XOR which can help us to find number of d in less complexity than this ?

- Is factoring polynomials as hard as factoring integers?
- $T(1) = 1 , T(n) = 2T(n/2) + n^3$? Divide and conquer
- How can I solve $8n^2 = 64n\,\log_2(n)$
- Minimum number of iterations in Newton's method to find a square root
- Continued fraction expansion related to exponential generating function
- Is 'every exponential grows faster than every polynomial?' always true?

Edit :

Eq: If `n=4`

and numbers are = `4 6 8 10`

then `d`

can be `{0,3}`

as

`4 ⊕ 6 ⊕ 8 ⊕ 10 =0`

and

`1 ⊕ 3 ⊕ 5 ⊕ 7 =0`

- Extended Euclidean algorithm with negative numbers
- Heuristics for topological sort
- What is the number of full binary trees of height less than $h$
- Longest increasing subsequence part II
- Continued fraction expansion related to exponential generating function
- how to solve the recurrence $T(n) = 2T(n/3) + n\log n$
- $n$-Bit Strings Not Containing $010$
- How do you check if a sequence of numbers is truly random?
- Any problem computable in $k$ memory slots can be computed with polynomials.
- A generalization of Kirkman's schoolgirl problem

You can figure out the possible values of `d`

one bit at a time. Consider the equation mod 2:

```
(A1-d) ⊕ (A2-d) ⊕ .......(A{n-1}-d) ⊕ (An-d) = 0 mod 2
```

Try 0 and 1 for `d`

, see if either works. Say d==1 is the only assignment that works. Then try the values 1 and 3 in the equation:

```
(A1-d) ⊕ (A2-d) ⊕ .......(A{n-1}-d) ⊕ (An-d) = 0 mod 4
```

and so on, taking all valid `d`

s mod `2^i`

and trying both `d`

and `d+2^i`

mod `2^{i+1}`

. The reason why this works is that both subtraction and xor do not propagate any information from higher bits to lower bits, so if you find a solution to the mod 2 equation, it remains a solution no matter what the higher-order bits of `d`

are set to.

The running time should be something like O(n * log Ak * #of solutions).

Example:

```
A = {9,12,23,30}
try d=0,1 mod 2. Both work.
try d=0,1,2,3 mod 4. All work.
try d=[0-7] mod 8. 1,3,5,7 work.
try d=[1,9,3,5,7] mod 16. 3,7 work. (no need to check if d>Ak)
now we've tried up to Ak, check the remaining solutions for the remaining
high-order bits. 3 and 7 work.
```

Example:

```
A = {4,6,8,10}
try d=0,1 mod 2. Both work.
try d=0,1,2,3 mod 4. All work.
try d=0,4,1,2,3 mod 8. All work.
at this point you've tried all d up to Ak. Do a final check and 0,3,4 work.
```

- The prime spectrum of a Dedekind Domain
- Total number of solutions of an equation
- The Velocities of the Contact Points of Two Rolling Curves are Equal at the Instant of Contact
- Jacobson radical of the integral group ring
- One last question on the concept of limits
- If $ 3x^2 + 2\alpha xy + 2y^2 + 2ax – 4y + 1 $ can be resolved into two linear factors, then prove the following.
- What are the most overpowered theorems in mathematics?
- How calculators do trigonometry
- Why do the Fibonacci numbers recycle these formulas?
- Today a student asked me $\int \ln (\sin x) \, dx.$
- Ramsey Number proof: $R(3,3,3,3)\leq 4(R(3,3,3)-1) + 2$
- Boxplots and bar graphs
- Maximum of $\frac{\sin z}{z}$ in the closed unit disc.
- Is Pythagoras the only relation to hold between $\cos$ and $\sin$?
- How I could define a inner product in the characters in $SL(2, \mathbb R)$