I have been taking tests for Internships and came across this coding problem, and I was not able to come up with a solution, Also I have not seen this kind of question on Leetcode given that I have solved 250+ questions. Problem: You are given two Integers N and X. You are required to create an array of N natural numbers such that *Bitwise XOR* of these numbers is equal to X. And the *sum of all the elements* in array is as *minimum* as possible. Consider Array in *non - decreasing* order. If multiple array exist then print the smallest among them. Input: N=3, X=2 Output: [1, 1, 2] I have not come across these kind of questions on Leetcode, so any suggestions for learning these will be helpful. Thanks!!
Can't tell if joking or not. If you can't solve this you don't deserve the job. (Did I mention I'm very, very ... uh, "not of sound mind" right now.)
I didn't understand your comment. Can you solve the question?
*Bitwise XOR* of a number with itself equals 0, y^y = 0. So essentially you're answer would be: [y,y,y,y,y,y,X] <--> y^y^y^y^y^y^X = 0 ^ X = X (that's the first part) To minimize the sum, if 0 is allowed, then y = 0, otherwise you can use y = 1 and your answer will be as follows [1,1,1,1,1,1,X] Also i believe there is a similar problem in Leetcode, the one to find the only non duplicate integer in an array of duplicates. Solution is XOR all elements and the result is your unique number. Hope it helps! Edit: based on counter examples and other below comments, this doesn't solve the problem correctly with regards to minimizing the sum. Please check below for more accurate answers. Leaving this answer though for XOR part,
Shame on yeh. Or maybe brilliant, letting the rabble in Makes you all look better
This is incorrect. For 13 3: 8 4 1 -> 13 13 1 1 -> 15
If N is odd, fill N-1 1s and the number X If N is even, fill N-2 1s and for the last two elements: if X is odd: Last two elements are X-1 and 1 If X is even: Last two elements are X+1 and 1 The idea with filling 1s is that, we are using the lowest allowed value and they cancel each other out. But when you can’t fill in an even number of 1s, you then accommodate the last 1, by manipulating X (either removing the last bit or adding the last bit) such that the XOR will get us the final result X
Hey, thanks for your solution.
This is wrong, see Google's comment above.
[0,0,....X] (edit answer is wrong, 0 not considered to be natural)
Look at the number of 1s in the binary representation of X. If num1s = n the array should be broken up by powers of 2 so each element gets a 1 in binary, e.g. for x=13,n=3 the solution is [8,4,1] (in binary, [1000,0100,0001] xor to 1101). If num1s is greater than n some 1s need to be combined. Eg [1100,0001] xor to 1101. If num1s is less than n some padding with 1s will need to be added. If n is greater than num1s by an even number, just add the padding, e.g. [1000,0100,0001,0001,0001] xor to 1101. If odd, 1 will need to be added to another term, e.g [1001,0100,0001,0001]. However this will fail if x=1 and n is even. In this case we need a solution like [11,10] or [11,10,01,01] etc.
Really cool Google. Thanks a lot. Can you please tell how you learnt to come up with such approaches? How much time did it take to be so good at problem solving and what platforms you use for coding? Thanks!!
I guess for me it's important to find the right way of visualizing a problem. In this case that was as a column of binary numbers. The place values that are supposed to xor to 1 need an odd number of 1s in the array, the 0s an even number. It's hard to give any general advice. I think as you learn algorithms and practice you find strategies for problem solving, and when you hear a new problem you try to fit it to one of those strategies. I guess 4 years (college)? Algorithms class, CS competitions (ACM ICPC), and "Cracking the Coding Interview" (book). I didn't know about LC when I was interviewing a couple years ago.
It's just each power of two in X and then some 1's to buffer if there is an even amount of space left. If there is an odd amount of space left, move two powers of two together and then fill rest with 1's (for example, N = 4, X = 7, then we get powers of two: 1 2 4. Now we have an odd amount of spaces left (1), so we move the 2 and 1 together to get 3 and fill the rest with two 1's to get 1 1 3 4. If there isn't enough space, then combine.
🍿
My solution: (beats 100%) 1. Divide x into as many powers of 2 as possible size of which is m (only 1 usage of each power start at highest power possible) 2. If m = n we are done 3. If m less than n N-m = remainder If remainder is even add in ones for the rest If remainder is odd If X is even add one to the previous non one and pad with 1’s If X is odd remove one to the previous non one and pad with 1’s 3. If M greater than n Combine the values in the overflow into the last cell
Is this on question on LC or any other platform? Can you share the link?
No I solved it for you, you’re welcome
Fuck me
Guy or girl?
Lol
If all numbers are Boolean this will be the solution: All zeros with with last element is 0 if x is true, 1 otherwise.
Array Should be of Natural numbers only. So 0 cannot be used.
Oh ok. Some consider 0 to be a natural number. It's a confusing term. :(