0

Recently came across a question --

Convert a decimal number(base 10) to binary number(base 2) but not the way we normally do. The algorithm is to be figured by us based on the following data--

0 = 000

1 = 001

2 = 011

3 = 010

4 = 110

5 = 111

6 = 101

7 = 100

13 = 1011

I tried really hard to come up with an algorithm but could not. Can someone think of a solution?

discoverAnkit
  • 1,141
  • 1
  • 11
  • 25
  • I think 6=101 and 7=100 are NOT right. Pair numbers should end with a 0 and not-pair numbers with a 1!! This does not seem to have sense at first ¿Could be the reason? – Alejandro Teixeira Muñoz Jun 30 '16 at 11:00
  • 3
    It's called "gray code", you can find the answer here : http://stackoverflow.com/questions/28841322/convert-decimal-to-gray-code-in-java – Jonathan Darryl Jun 30 '16 at 11:01
  • Nice, Thanks!! Did not know about!! – Alejandro Teixeira Muñoz Jun 30 '16 at 11:04
  • Hard to pick a dupe, but I think the code golf question is the best fit -- it contains many different programs that output n-bit gray codes. Given how simple the solution is (essentially `bin(n ^ (n >> 1)))`) the code golf solutions contain mostly reasonable code. – Paul Hankin Jun 30 '16 at 11:15
  • How does one think about it? I had no idea about Code Golf. Its really difficult to reach n^(n>>1) through hit n trial. – discoverAnkit Jun 30 '16 at 11:18
  • @ankitG the question is unfair -- unless you know about gray codes it's not so easy to spot the pattern given so little data. But one approach given any sequence is to search OEIS for it, and that works here: https://oeis.org/search?q=0%2C+1%2C+3%2C+2%2C+6%2C+7%2C+5%2C+4&sort=&language=&go=Search – Paul Hankin Jun 30 '16 at 11:26
  • @PaulHankin I didn't know about OEIS as well. Good thing. Bcoz of this question I learnt about Gray Codes and OEIS. – discoverAnkit Jun 30 '16 at 11:28

1 Answers1

0

What's really interesting about your conversions is that successive numbers differ by one digit. This is characteristic for Gray code.

For more information visit wikipedia or Geeks4geeks.

Algorithm:

  • Write binary representation of the number
  • Shift right it's copy (remove last bit - lose it).
  • XOR all bits. It will return Gray code.
xenteros
  • 15,586
  • 12
  • 56
  • 91
  • Yep. This thing was mentioned in the question too that successive binary representations differ by one bit. I had no idea about Gray Code. But I am still wondering how would 1 go about solving this problem if one has never heard of Gray code before – discoverAnkit Jun 30 '16 at 11:21
  • Ask Gray :) I have added the easiest algorithm for finding number's Gray code. Don't worry, on each CS studies you would be tought of Gray code. – xenteros Jun 30 '16 at 11:28