{"id":1549,"date":"2020-06-11T09:30:23","date_gmt":"2020-06-11T09:30:23","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1549"},"modified":"2022-03-22T11:40:46","modified_gmt":"2022-03-22T11:40:46","slug":"power-of-2","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/power-of-2\/","title":{"rendered":"Power Of 2"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used<\/h3>\n
\n

Strings, Mathematics<\/p>\n<\/blockquote>\n

Difficulty Level<\/h3>\n
\n

Hard<\/p>\n<\/blockquote>\n

Problem Statement (Simplified):<\/h3>\n
\n

Find if the number given as a string is the power of two or not. Return 1 if yes, else 0.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

Test Case<\/h4>\n
Input:\n2\n16\n99\n\nOutput:\n1\n0\n\nExplanation:\nCase-1:\n16 can be represented as  2^4, hence it is a power of two, so we print 1.\n\nCase-2:\n99 is not a power of two, we print 1.<\/code><\/pre>\n
Solving Approach :<\/h3>\n
Bruteforce Approach:<\/h4>\n
\n
1) Convert string number into an integer or long long int.
\n2) Check if the number is the power of two by dividing it by 2 repeatedly.
\n3) This Approach is only suitable for numbers of length 1<\/code> – 1020<\/sup><\/p>\n<\/blockquote>\n
Efficient Approach :<\/h4>\n
As a larger number cannot be taken as an integer, we take input as a string.<\/p>\n
    \n
  1. \n
    We first check if the string is a single digit and have value 1 or not, if yes we return 0 because we need to check if the number is the power of 2 greater than 1.<\/p>\n<\/li>\n
  2. \n
    If that condition fails, we divide the string by 2 repeatedly using the conventional method of digit by digit division until we get a value 1 or any odd number.<\/p>\n<\/li>\n
  3. \n
    If the number becomes odd in the procedure we return 0 and get out of the loop. Else we continuously divide.<\/p>\n<\/li>\n
  4. \n
    After the loop, if we receive 1 that means the number was the power of two and after continuous division only 1 is left. So we return 1.<\/p>\n<\/li>\n<\/ol>\n
    Example<\/h3>\n
    \n
      \n
    • Let’s take 32<\/code> as an example here:<\/li>\n<\/ul>\n
      Step-1, Number = 32 :<\/em><\/strong> <\/p>\n
        \n
      • \n
        Last index have an even number, so we can move on two next step.<\/p>\n<\/li>\n
      • \n
        We divide this number character by character.<\/p>\n<\/li>\n<\/ul>\n<\/blockquote>\n
        \"\"<\/p>\n
        \n
          \n
        • \n
          3<\/code> at index is odd and on division gives 1<\/code> as quotient and also 1<\/code> as remainder, so we replace current value in string by quotient, and carry remainder to next value.<\/p>\n<\/li>\n
        • \n
          2<\/code> at index is even, but we have an carry (1<\/code>) from last digit, so we add 10<\/code> to current value. Current value becomes 12<\/code>, so we divide it now by 2<\/code>,no remainder is carried. Quotient 12\/2<\/code> i.e. 6<\/code> replaces the current value. So, current value becomes 6<\/code>.<\/p>\n<\/li>\n
        • \n
          So after, first division, our number becomes 16<\/code>.<\/p>\n
          Step-2, Number = 16 :<\/em><\/strong>  <\/p>\n<\/li>\n
        • \n
          Last index have an even number, so we can move on two next step.<\/p>\n<\/li>\n
        • \n
          We again divide this number character by character.<\/p>\n<\/li>\n<\/ul>\n<\/blockquote>\n
          \"\"<\/p>\n
          \n
            \n
          • \n
            1<\/code> at current index is less than 2<\/code>, so it will be taken as carry to next digit. Also, we replace current character by 0<\/code>.<\/p>\n<\/li>\n
          • \n
            6<\/code> at current index is divisible by 2<\/code>, but we also have a 1<\/code> as carry from the last digit, so we add 10<\/code> to the current value, making it 16<\/code>. We then replace current character by Quotient 16\/2<\/code> i.e.8<\/code>, hence our final number becomes 08<\/code>. We drop 0<\/code> from the start as it will have no significance.<\/p>\n
            Step-3, Number = 8 :<\/em><\/strong>  <\/p>\n<\/li>\n
          • \n
            Last index have an even number, so we can move on two next step.<\/p>\n<\/li>\n
          • \n
            We again divide this number character by character.<\/p>\n<\/li>\n<\/ul>\n<\/blockquote>\n
            \"\"<\/p>\n
            \n
              \n
            • \n
              Last index have an even number, so we can move on two next step.<\/p>\n<\/li>\n
            • \n
              8<\/code> at current index is divisible by 2<\/code> also we don’t have any carry. So, We replace current character by Quotient 8\/2<\/code> i.e.4<\/code>, hence our final number becomes 4<\/code>.<\/p>\n
              Step-4, Number = 4 :<\/em><\/strong>  <\/p>\n<\/li>\n
            • \n
              Last index have an even number, so we can move on two next step.<\/p>\n<\/li>\n
            • \n
              We again divide this number character by character.<\/p>\n<\/li>\n<\/ul>\n<\/blockquote>\n
              \"\"<\/p>\n
              \n
                \n
              • \n
                4<\/code> at current index is divisible by 2<\/code> also we don’t have any carry. So, We replace current character by Quotient 4\/2<\/code> i.e.2<\/code>, hence our final number becomes 2<\/code>.<\/p>\n
                Step-5, Number = 2 :<\/em><\/strong>  <\/p>\n<\/li>\n
              • \n
                Last index have an even number, so we can move on two next step.<\/p>\n<\/li>\n
              • \n
                We again divide this number character by character.<\/p>\n<\/li>\n<\/ul>\n<\/blockquote>\n
                \"\"<\/p>\n
                \n
                  \n
                • 2<\/code> at current index is divisible by 2<\/code> also we don’t have any carry. So, We replace current character by Quotient 2\/2<\/code> i.e.1<\/code>, hence our final number becomes 1<\/code>.<\/li>\n<\/ul>\n
                  Final step:<\/em><\/strong><\/p>\n
                    \n
                  • \n
                    As we can see our string has a length of 1<\/code> now, so we check if the last digit is 1<\/code> or not. If yes, given value was the power of 2<\/code>, else it is not.<\/p>\n<\/li>\n
                  • \n
                    Given number has 1<\/code> in last, so given number was a power of two, so we print 1<\/code> as answer. <\/p>\n<\/li>\n<\/ul>\n<\/blockquote>\n
                    Solutions<\/h3>\n\t\t\t\t\t\t