2

I am trying to check if a number (input as a String) is a power of 2. The problem is that the number might be greater than 2^64 (long long limit). If I store it in double then I cannot do binary operations on it (so the trick v & (v - 1) == 0 does not work). Here is the solution I stumbled upon:

public class Solution {
    public int power(String A) {

        String dividend = A;
        StringBuilder str;

        if (A == null || A.length() == 0)
            return 0;

        if (A.length() == 1 && A.charAt(0) == '0')
            return 0;

        while (dividend.length() > 0 && !dividend.equalsIgnoreCase("2")) {
            str = new StringBuilder();
            int carry = 0;
            int n = dividend.length();

            if (n > 0) {
                int num = dividend.charAt(n - 1) - '0';

                if (num % 2 == 1)
                    return 0;
            }

            for (int i = 0; i < n; i++) {

                char c = (char) (dividend.charAt(i) - '0');
                int res = c + 10 * carry;

                c = (char) (res / 2 + '0');
                carry = res % 2;

                str.append(c);
            }

            if (str.charAt(0) == '0')
                str.deleteCharAt(0);

            dividend = str.toString();
        }

        return 1;

    }

}

I am having problems understanding the solution. The first check is done if a number is odd or not. I am having problems understanding the implementation of the manual division done in this problem (especially the arithmetic operations involving both char and int). I get that '0' == 48 and subtracting '0' from a character converts it into integer value. Can anyone explain to me how this division operation has been implemented here? Thanks!

Turing85
  • 18,217
  • 7
  • 33
  • 58
Aastik
  • 43
  • 1
  • 4

3 Answers3

0

The easiest way to understand this implementation is a pen and paper test. I will skip the part you understood and focus only on the last for loop.

Let's take "50" as an example-input. The loop steps through the String character-wise, starting on the left. Therefore, the first character processed is the '5'. As you know, 5 is odd. This means we have to "carry" something into the next division. The result of 5 / 2 is 2. This 2 will be the first digit of the result in the division. Notice that if we reverse our steps, we get 2 * 2, which is 4. This is the reason we have to carry something over (the 1 missing, since 5 - 4 is 1). You may notice that, if you divide by 2, you can either carry 0 (nothing) or 1 (if and only if the dividend is odd).

Now on to the next digit, which is 0. We have to carry the 1 from the last division over to this step. Since we moved one digit to the left, a 1 from the previos step becomes a 10 in this step. We moved "one order of magnitude down", therefore we have to multiply the carryed part by 10. This means we calculate (0 + (1 * 10)) / 2, which is 10 / 2 = 5. This 5 is the second digit of the result. Since the dividend is even, we need nothing to carry over.

The final ouput therefore is "25", as expected.

Turing85
  • 18,217
  • 7
  • 33
  • 58
0
    str = new StringBuilder();
    int carry = 0;
    int n = dividend.length();

    if (n > 0) {
        int num = dividend.charAt(n - 1) - '0';

divided is input. It takes character at the end of string, and from that value takes value of '0' http://www.asciitable.com/ - for '0' it is 48. So it gives value of that decimal w/o any parsing.

        if (num % 2 == 1)
            return 0;
    }

Next for loop divides divided by two. It is done by dididing each digit. Starting from first one till last. Next iteration gets carry value from prev. 

    for (int i = 0; i < n; i++) {

        char c = (char) (dividend.charAt(i) - '0');

As before goes here - it 'c' is byte with decimal value. 

        int res = c + 10 * carry;

'res' has also carry. 

        c = (char) (res / 2 + '0');

Division of particular entry is done here. Adding '0' is simple conversion to character / string, 

        carry = res % 2;

Note that we are going from start, not from the end. So carry that goes to next iteration is modulo. 

        str.append(c);
    }

    if (str.charAt(0) == '0')
        str.deleteCharAt(0);

Just remove leading zeros 

    dividend = str.toString();

Convert back to string, and call divide once again.

Michał Zaborowski
  • 3,911
  • 2
  • 19
  • 39
0

//try this!

    double n = scanner.nextInt();

    while (n > 1) {
        n = n / 2;
    }
    System.out.println(n);
    if (n == 1)
        System.out.println("true");
    else
        System.out.println("false");
amanj.amjadi
  • 1
  • 2