To reach the target number from 0 in minimum number of steps

Question

Problem Statement: Find the minimum number of steps required to reach a target number x from 0 (zero), using only two operations: +1 (add 1 to the number) or *2 (multiply 2 with the number).

So here's the Logic that I came up with:

The best way is to work backwards. Start from the number you need:

Subtract 1 if the number is odd.
Divide by 2 if the number if even.
Stop when you get to zero.

For example, for 29, you get 28, 14, 7, 6, 3, 2, 1, 0.

And, here's what I have tried doing (Java 7):

kValues is an array that has the x values for which the steps are needed to be computed and stored in an array called result.

static int[] countOperationsToK(long[] kValues) {
    int size = kValues.length,x,i,steps;
    int result[] = new int[size];

    for (i = 0; i < size; ++i)
    {
        steps = 0;
        for (x = (int)kValues[i]; x != 0 ; ++steps)
        {
            if((x % 2) == 0)
                x /= 2;
            else x--;
        }
        result[i] = steps;
    }

    return result;
}

My Problem:

This is a Hackerrank question and I am supposed to write an efficient code. I was successful with 7/11 test cases and others were timed out. Since, it is a Hackerrank question, I can't change the function definition or the return type. That is the reason why I am converting from long to int in my for loop, in order to use % (modulus). I would like to know where I am going wrong. Is my algorithm taking too long to compute (for the number of values close to a million)? Which is obviously the case, but how do I alter my algorithm in order to pass all the test cases?

Thank you in advance :)

This is tagged under python too because, I think python can give a better solution. So, if by chance any python guy sees this code and be like "I can reduce the time complexity in seconds". So yeah... @Stael — Prakhar Saxena, Sep 11 '17 at 16:19
The cast is likely causing problems. See [here](https://stackoverflow.com/questions/5737616/what-is-the-modulo-operator-for-longs-in-java) to use modulo on `long`s. — Andrew S, Sep 11 '17 at 16:22

Andy Turner · Answer 1 · 2017-09-11T16:24:11.993

1

for (x = (int)kValues[i]; x != 0 ; ++steps)

The fact that you are casting a long to an int is very suspicious. You might get a negative number when you do that.

Say x == -2: you divide it by 2 to give -1, then subtract 1 to give -2. You'll keep doing that indefinitely.

Just define x to be a long, and remove the cast.

edited Sep 11 '17 at 16:24

answered Sep 11 '17 at 16:20

Andy Turner

137,514
11
162
243

If I do that, I cant use the modulus in my logic – Prakhar Saxena Sep 11 '17 at 16:22
2

@Prakhar why? `%` is defined for long. But you could simply test `(num & 1) == 0` alternatively. – Andy Turner Sep 11 '17 at 16:25

score 0 · Answer 2 · answered Sep 11 '17 at 16:28

So, here's the working code. I had forgotten to append L while using the modulo. Silly mistake led to so much of typing. LOL!!

static int[] countOperationsToK(long[] kValues) {
    int size = kValues.length,i,steps;
    int result[] = new int[size];
    long x;

    for (i = 0; i < size; ++i)
    {
        steps = 0;
        for (x = kValues[i]; x != 0 ; ++steps)
        {
            if((x % 2L) == 0)
                x /= 2L;
            else x -= 1L;
        }
        result[i] = steps;
    }

    return result;
}

There is no need for those `L`s. Whenever you use a binary operator with long and int operands, the int will automatically be promoted to a long. — Andy Turner, Sep 11 '17 at 16:31

score 0 · Answer 3 · answered Sep 11 '17 at 17:05

Here is a very short version, using bit-analysis:

static int[] countOperationsToK(long... input) {
    int result[] = new int[input.length];
    for (int i = 0; i < input.length; i++)
        if (input[i] > 0)
            result[i] = Long.bitCount(input[i]) + 63 - Long.numberOfLeadingZeros(input[i]);
    return result;
}

The idea here is to look at the binary number, e.g. for 29 that is 11101. There are 4 bits set, so we'd need to do +1 four times, and the highest bit position is 4, so we need to left-shift (i.e. *2) four times, for a total of 8 operations: +1, *2, +1, *2, +1, *2, *2, +1.

numberOfBits = Long.bitCount(x)
highBitNumber = floor(log2(x)) = 63 - Long.numberOfLeadingZeros(x)

The highBitNumber part doesn't work if value is zero, hence the if statement.

score 0 · Answer 4 · answered Mar 04 '19 at 09:49

0

For input number x,

Minimum no. of Ops = (int)log2(x) + Long.BitCount(x)

answered Mar 04 '19 at 09:49

Aanand Kumar

76
6

To reach the target number from 0 in minimum number of steps

4 Answers4