package prac;

import java.util.Scanner;

public class ReversedBinary {

    public static void main(String[] args) {
        int number;

        // Scanner in = new Scanner(System.in);

        // System.out.println("Enter a positive integer");
        // number = in.nextInt();
        // number = 1041;
        // number = 126;
        // number = 122;
        number = 98;

        if (number < 0) {
            System.out.println("Error: Not a positive integer");
        } else {
            ReversedBinary reversedBinary = new ReversedBinary();
            System.out.println(reversedBinary.solution(number));
        }
    }

    // O(n)
    public int solution(int N) {

        // System.out.print("Convert to binary is:");
        // System.out.print(binaryform(number));
        int maxBinaryGapLen = 0;

        /** convert int into binaray string **/
        StringBuilder sb = new StringBuilder();
        convertIntToBinaryString(N, sb); // O(n)
        String numberInBinary = sb.toString();


        String[] words = numberInBinary.split("");
        int length = words.length;
        int firstOneIndex = -1;
        int secondOneIndex = -1;
        for (int i = 0; i < length; i++) { // O(n)
            if ("1".equals(words[i])) {

                /** 若已經曾經有過一對,則兩個一同往前移動 **/
                if (firstOneIndex != -1 && secondOneIndex != -1) {
                    firstOneIndex = secondOneIndex;
                    secondOneIndex = i;
                /** 若為第一個找到的1, 則更新firstOneIndex **/
                } else if (firstOneIndex == -1) {
                    firstOneIndex = i;
                /** 若為第二個找到的1, 則更新secondOneIndex **/
                } else if (firstOneIndex != -1) {
                    secondOneIndex = i;
                }

                /** 若有secondOneIndex則計算看看 **/
                if (secondOneIndex != -1) {
                    int currGapLen = getBinaryGapLen(firstOneIndex, secondOneIndex);
                    // System.out.println("firstOneIndex: " + firstOneIndex);
                    // System.out.println("secondOneIndex: " + secondOneIndex);
                    // System.out.println("currGapLen: " + currGapLen);
                    if (currGapLen > maxBinaryGapLen)
                        maxBinaryGapLen = currGapLen;
                }
            } // end of if ("1".equals(length))
        } // end of for

//      System.out.println("maxBinaryGapLen: " + maxBinaryGapLen);
        return maxBinaryGapLen;
    }

    private static int getBinaryGapLen(int firstOneIndex, int secondOneIndex) {
        return secondOneIndex - (firstOneIndex + 1);
    }

    private static void convertIntToBinaryString(int number, StringBuilder sb) {
        // System.out.println("number: " + number);

        // 取最後一個binary的餘數
        int remainder = number % 2;
        // System.out.println("remainder: "+ remainder);

        // 將餘數放到最前面
        sb.insert(0, remainder);

        // 終止條件
        if (number <= 1) {
            return; // KICK OUT OF THE RECURSION
        }

        int number2 = number >> 1; // 全部往右移一格
        convertIntToBinaryString(number2, sb);
        // sb.append(remainder);
    }
}