Java || 👍Explained in Detail👍|| Fast O(N) Solution✅|| Bit Manipulation & Math
I do my best everyday to give a clear explanation, so to help everyone improve their skills.\n\nIf you find this helpful, please \uD83D\uDC4D upvote this post a
I do my best everyday to give a clear explanation, so to help everyone improve their skills.\n\nIf you find this **helpful**, please \uD83D\uDC4D **upvote** this post and watch my [Github Repository](https://github.com/cheehwatang/leetcode-java).\n\nThank you for reading! \uD83D\uDE04 Comment if you have any questions or feedback.\n\n---\n\n**Java (Bit Manipulation) - Clean Code**\n\n```\nclass Solution {\n    public int concatenatedBinary(int n) {\n        final long modulo = (long) (1e9 + 7);\n        long result = 0;\n        int binaryDigits = 0;\n        for (int i = 1; i <= n; i++) {\n            if ((i & (i - 1)) == 0) binaryDigits++;\n            result = ((result << binaryDigits) + i) % modulo;\n        }\n        return (int) result;\n    }\n}\n```\n\n**Java (Bit Manipulation) - With Explanation**\n\n```\n// Time Complexity: O(N)\n// Space Complexity: O(1)\n// where N is n.\nclass Solution {\n\n    // Approach:\n    // Using bit manipulation as described below.\n    // A bit of description for the bitwise operations used, if you are not familiar.\n    // 1. & - Bitwise AND operation:\n    //    0 & 0 = 0,\n    //    1 & 0 = 0,\n    //    1 & 1 = 1.\n    //    Example : 1101 & 1010 = 1000\n    //\n    // 2. << - Shift Left operation, by n position:\n    //    Example:\n    //    11 (3) << 2 (n position) = 1100 (14)\n    //\n\n    public int concatenatedBinary(int n) {\n\n        final long modulo = (long) (1e9 + 7);\n        long result = 0;\n\n        // This records the number of binaryDigits we need to shift left.\n        int binaryDigits = 0;\n\n        for (int i = 1; i <= n; i++) {\n\n            // If i is a power of 2, we add one additional binaryDigits to shift.\n            // Example:\n            // i = 8 (1000), i-1 = 7 (111)\n            // i & (i-1) = 1000 & 111 = 0\n            // So we know we have increased the binaryDigits from 3 (in 111) to 4 (in 1000).\n            if ((i & (i - 1)) == 0) {\n                binaryDigits++;\n            }\n\n            // With the updated binaryDigits, we now can concatenate i to the result.\n            // Each time get the remainder of the result % modulo.\n            // Example:\n            // i = 2\n            // result = 1 (1) << 2 (n position) + 10 (2) = 100 (4) + 10 (2) = 110 (6).\n            // i = 3\n            // result = 110 (6) << 2 (n position) + 11 (3) = 11000 (24) + 11 (3) = 11011 (27).\n            //\n            result = ((result << binaryDigits) + i) % modulo;\n        }\n        return (int) result;\n    }\n}\n```\n\n**Java (Math) - With Explanation**\n```\nclass Solution {\n    \n    // Approach:\n    // We concatenate by shifting position of result with division and multiplication, then add the number.\n    // As there are a lot of repetitions in shifting of positions, it is much less efficient than using bit manipulation.\n    \n    public int concatenatedBinary(int n) {\n        final long modulo = (long) (1e9 + 7);\n        long result = 0;\n        for (int i = 1; i <= n; i++) {\n            // For each i, we shift left the position of result with * 2,\n            // while shifting right the position of i with / 2.\n            int temp = i;\n            while (temp > 0) {\n                temp /= 2;\n                result *= 2;\n            }\n            // Add the i to the result and get the remainder of modulo.\n            result = (result + i) % modulo;\n        }\n        return (int) result;\n    }\n}\n```\n
['Math', 'Bit Manipulation', 'Java']