import java.util.ArrayList; import java.util.Arrays; import java.util.LinkedList; import java.util.Scanner; public class Yuki003 { int bitCount(int value) { int count = 0; while (value > 0) { count += value % 2; value /= 2; } return count; } Yuki003() { Scanner scanner = new Scanner(System.in); int N = scanner.nextInt(); System.out.println(search(N)); } private int search(final int N) { boolean[] visit = new boolean[N + 1]; ArrayList list = new ArrayList<>(); list.add(1); int move = 1; visit[1] = true; while (list.size() > 0) { ArrayList next = new ArrayList<>(); for (int i = 0; i < list.size(); i++) { final int value = list.get(i); if (value == N) { return move; } int bit = bitCount(value); int prev = value - bit; int nxt = value + bit; if (1 <= prev && !visit[prev]) { next.add(prev); visit[value] = true; } if (nxt <= N && !visit[nxt]) { next.add(nxt); visit[value] = true; } } list = next; move++; } return -1; } public static void main(String[] args) { new Yuki003(); } }