Can you solve this coding problem?

New
wMAw04

New

wMAw04
Sep 8, 2019 32 Comments

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!!

Google Microsoft Uber
32

comments

Want to comment? LOG IN or SIGN UP
  1. TOP
  2. RECENT
  3. OLD
 TOP 32 Comments
  • Rubrik
    dat_guy123

    Go to company page Rubrik

    dat_guy123
    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
    Sep 8, 2019 5
    • Oath
      meal

      Go to company page Oath

      meal
      That was my initial thought, but it doesn't guarantee the minimal sum of elements. Consider N=3 and X=7. In your solution, you'll get [1, 1, 7], whose sum is 9. A smaller solution is [1, 2, 4].
      So, the solution would be first spreading N's bits over as many elements as possible, and then place 1s at the rest of the elements (omitting edge cases for laziness).
      Sep 8, 2019
    • Please see my solution below
      Sep 9, 2019
  • Amazon
    trek34

    Go to company page Amazon

    trek34
    If all numbers are Boolean this will be the solution: All zeros with with last element is 0 if x is true, 1 otherwise.
    Sep 8, 2019 2
    • New
      wMAw04

      New

      wMAw04
      OP
      Array Should be of Natural numbers only.
      So 0 cannot be used.
      Sep 8, 2019
    • Oh ok. Some consider 0 to be a natural number. It's a confusing term. :(
      Sep 8, 2019
  • Google / Eng
    d3j88wq

    Go to company page Google Eng

     d3j88wq
    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.
    Sep 8, 2019 2
    • New
      wMAw04

      New

      wMAw04
      OP
      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!!
      Sep 8, 2019
    • Google / Eng
      d3j88wq

      Go to company page Google Eng

       d3j88wq
      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.
      Sep 8, 2019
  • Google
    Larry Pаge

    Go to company page Google

    Larry Pаge
    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.
    Sep 8, 2019 0
  • Yahoo
    Genius

    Go to company page Yahoo

    Genius
    *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,
    Sep 8, 2019 4
    • I think you give the right approach Google. You can remove uncessesary 1's by having the first elements set each bit correctly ([1,2,4,8,.. skipping unessesary bits). Then pad the rest with 1s. You also have to handle the case where there's not enough room in the array but that's fairly trivial.
      Sep 8, 2019
    • Rubrik
      dat_guy123

      Go to company page Rubrik

      dat_guy123
      Pandora, Google : Yes that seems right. So essentially we are splitting X into as many cells as possible (based on the number of bits we need set) and then fill the rest with 1s.
      So we are trying to minimize the number of additional 1s we need to add, thus minimizing the total sum of the array
      Sep 8, 2019