89. Gray Code Medium

1/**
2 * [89] Gray Code
3 *
4 * An n-bit gray code sequence is a sequence of 2^n integers where:
5 * 
6 * Every integer is in the inclusive range [0, 2^n - 1],
7 * The first integer is 0,
8 * An integer appears no more than once in the sequence,
9 * The binary representation of every pair of adjacent integers differs by exactly one bit, and
10 * The binary representation of the first and last integers differs by exactly one bit.
11 * 
12 * Given an integer n, return any valid n-bit gray code sequence.
13 *  
14 * Example 1:
15 * 
16 * Input: n = 2
17 * Output: [0,1,3,2]
18 * Explanation:
19 * The binary representation of [0,1,3,2] is [00,01,11,10].
20 * - 0<u>0</u> and 0<u>1</u> differ by one bit
21 * - <u>0</u>1 and <u>1</u>1 differ by one bit
22 * - 1<u>1</u> and 1<u>0</u> differ by one bit
23 * - <u>1</u>0 and <u>0</u>0 differ by one bit
24 * [0,2,3,1] is also a valid gray code sequence, whose binary representation is [00,10,11,01].
25 * - <u>0</u>0 and <u>1</u>0 differ by one bit
26 * - 1<u>0</u> and 1<u>1</u> differ by one bit
27 * - <u>1</u>1 and <u>0</u>1 differ by one bit
28 * - 0<u>1</u> and 0<u>0</u> differ by one bit
29 * 
30 * Example 2:
31 * 
32 * Input: n = 1
33 * Output: [0,1]
34 * 
35 *  
36 * Constraints:
37 * 
38 * 1 <= n <= 16
39 * 
40 */
41pub struct Solution {}
42
43// problem: https://leetcode.com/problems/gray-code/
44// discuss: https://leetcode.com/problems/gray-code/discuss/?currentPage=1&orderBy=most_votes&query=
45
46// submission codes start here
47
48impl Solution {
49    pub fn gray_code(n: i32) -> Vec<i32> {
50        let mut result = vec![];
51        for i in 0..1 << n {
52            result.push(i ^ i >> 1)
53        }
54        result
55    }
56}
57
58// submission codes end
59
60#[cfg(test)]
61mod tests {
62    use super::*;
63
64    #[test]
65    fn test_89() {
66        println!("Got {:#?}", Solution::gray_code(2));
67    }
68}
69