You are viewing a single comment's thread. Return to all comments →
The 'n can be up to 10^5' information in the problem description suggests that we need to think a non-brute-force approach here.
So, thinking this through... from the example 10 (decimal) = 1010 (binary) ... has solutions ... 0 1 100 0101
10 (decimal) = 1010 (binary) ... has solutions ... 0 1 100 0101
Which means that we're looking for all the permutation of numbers with '1s' in the '0s' of the binary representation of the input number.
` def sumXor(n): if n == 0: return 1
binary = bin(n) zeros = binary.lstrip('0b').count('0') return 2 ** zeros
Seems like cookies are disabled on this browser, please enable them to open this website
Sum vs XOR
You are viewing a single comment's thread. Return to all comments →
The 'n can be up to 10^5' information in the problem description suggests that we need to think a non-brute-force approach here.
So, thinking this through... from the example
10 (decimal) = 1010 (binary) ... has solutions ... 0 1 100 0101
Which means that we're looking for all the permutation of numbers with '1s' in the '0s' of the binary representation of the input number.
The 'n can be up to 10^5' information in the problem description suggests that we need to think a non-brute-force approach here.
So, thinking this through... from the example
10 (decimal) = 1010 (binary) ... has solutions ... 0 1 100 0101
Which means that we're looking for all the permutation of numbers with '1s' in the '0s' of the binary representation of the input number.
` def sumXor(n): if n == 0: return 1
` def sumXor(n): if n == 0: return 1