#include using namespace std; #define MAX 10000000 int q[MAX]; int head = 0, tail = 0; void enq(int p) { q[tail] = p; ++tail; if (tail >= MAX) { tail = 0; } } bool deq(int* p) { if (head == tail) { return false; } else { *p = q[head]; ++head; if (head >= MAX) { head = 0; } return true; } } int BinaryCount(int a) { int cnt = 0; while (a>0) { cnt++; a &= a - 1; } return cnt; } int main(void) { int n; cin >> n; int* count = new int[n+1]; for (int i = 1; i <= n; ++i) { count[i] = MAX; } int posi = 1, hosuu; count[posi] = 1; do { hosuu = BinaryCount(posi); if (posi - hosuu > 0 && count[posi - hosuu] > count[posi]) { count[posi - hosuu] = count[posi] + 1; enq(posi - hosuu); } if (posi + hosuu <= n && count[posi + hosuu] > count[posi]) { count[posi + hosuu] = count[posi] + 1; enq(posi + hosuu); } } while (deq(&posi)); if (count[n] != MAX) { cout << count[n] << endl; } else { cout << "-1" << endl; } return 0; }