|
|
back to boardO(1) solution sol(1 x) = x - 2 * (popcount(x) - 1) - popcount(x ^ (x - 1)) In GCC you have the builtin function __builtin_popcount. For MSVC, the builtin __popcnt doesn't seem to be available on the server, but you can easily find an O(1) implementation on the Internet. Re: O(1) solution Posted by knok16 20 Jun 2015 15:23 Hi, How can it be proved, deduced? Thanks. Re: O(1) solution Posted by esbybb 18 Sep 2015 11:17 public static void main(String[] args) throws FileNotFoundException { InputStream is = System.in; Scanner sc = new Scanner(new InputStreamReader(is)); int distance = from1toN(sc.nextInt()) - from1toN(sc.nextInt()); if (distance>0) System.out.println(distance); else System.out.println(-distance); }
static int from1toN(int n) { int j = Long.bitCount(n)-1; return n - j - j - thefirstIndexOfOne(n); }
static int thefirstIndexOfOne(int n) { int inx = 1; while(n>0) { if ((n&1)==1) break; n/=2; inx++; } return inx; } Re: O(1) solution Posted by esbybb 18 Sep 2015 11:25 N xor (N-1) = the first index of one of N - you learn something everyday Re: O(1) solution Posted by esbybb 18 Sep 2015 11:46 1 1 0 1 2 0 1 3 0 1 4 1 4 - 2*(c_of_ones[100]-1) - 3 (TO level, leafs level=1) 1 5 2 1 6 2 1 7 2 1 8 4 8 - 2*(c_of_ones[1000]-1) - 4 (TO level, leafs level=1) 1 9 6 1 10 6 10 - 2*(c_of_ones[1010]-1) - 2 (TO level, leafs level=1) 1 11 6 11 - 2*(c_of_ones[1011]-1) - 1 (TO level, leafs level=1) 1 12 7 12 - 2*(c_of_ones[1100]-1) - 3 (TO level, leafs level=1) 1 13 8 1 14 8 1 15 8 1 16 11
int j = Long.bitCount(n)-1; return n - j - j - thefirstIndexOfOne(n); 16 8 4 12 2___6 10 14 1_3 5_7 _ 9_11 13_15 _ Edited by author 18.09.2015 11:47 |
|
|