Number of steps to reduce a number in binary representation to 1

user_19786266 0
Viewed 136

Given the binary representation of an integer as a string s, return the number of steps to reduce it to 1 under the following rules:

If the current number is even, you have to divide it by 2.

If the current number is odd, you have to add 1 to it.

It is guaranteed that you can always reach one for all test cases.

Step 1) 13 is odd, add 1 and obtain 14.

Step 2) 14 is even, divide by 2 and obtain 7.

Step 3) 7 is odd, add 1 and obtain 8.

Step 4) 8 is even, divide by 2 and obtain 4.

Step 5) 4 is even, divide by 2 and obtain 2.

Step 6) 2 is even, divide by 2 and obtain 1.

My input = 1111011110000011100000110001011011110010111001010111110001

Expected output = 85

My output = 81

For the above input, the output is supposed to be 85. But my output shows 81. For other test cases it seems to be giving the right answer. I have been trying all possible debugs, but I am stuck.

#include <iostream>
#include <string.h>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
int main()
{
  string s = 
     "1111011110000011100000110001011011110010111001010111110001";
  long int count = 0, size;
  unsigned long long int dec = 0;
  size = s.size();
  // cout << s[size - 1] << endl;
  for (int i = 0; i < size; i++)
  {
   // cout << pow(2, size - i - 1) << endl;
    if (s[i] == '0')
        continue;
    // cout<<int(s[i])-48<<endl;
    dec += (int(s[i]) - 48) * pow(2, size - 1 - i);
  }
  // cout << dec << endl;
  //  dec = 278675673186014705;

  while (dec != 1)
  {

    if (dec % 2 == 0)
        dec /= 2;
    else
        dec += 1;
    count += 1;
  }

  cout << count;
  return 0;

}

c++
2 Answers

This line:

pow(2, size - 1 - i)

Can face precision errors as pow takes and returns doubles.

Luckily, for powers base 2 that won't overflow unsigned long longs, we can simply use bit shift (which is equivalent to pow(2, x)).

Replace that line with:

1LL<<(size - 1 - i)

So that it should look like this:

dec += (int(s[i]) - 48) * 1ULL<<(size - 1 - i);

And we will get the correct output of 85.

Note: as mentioned by @RSahu, you can remove (int(s[i]) - 48), as the case where int(s[i]) == '0' is already caught in an above if statement. Simply change the line to:

dec += 1ULL<<(size - 1 - i);
user_119830460

The core problem has already been pointed out in answer by @Ryan Zhang.

I want to offer some suggestions to improve your code and make it easier to debug.

  1. The main function has two parts -- first part coverts a string to number and the second part computes the number of steps to get the number to 1. I suggest creating two helper functions. That will allow you to debug each piece separately.

    int main()
{
    string s = "1111011110000011100000110001011011110010111001010111110001";
    unsigned long long int dec = stringToNumber(s);
    cout << "Number: " << dec << endl;
    //  dec = 278675673186014705;

     int count = getStepsTo1(dec);
    cout << "Steps to 1: " << count << endl;
    return 0;
}

  2. Iterate over the string from right to left using std::string::reverse_iterator. That will obviate the need for size and use of size - i - 1. You can just use i.

    unsigned long long stringToNumber(string const& s)
{
    size_t i = 0;
    unsigned long long num = 0;
    for (auto it = s.rbegin(); it != s.rend(); ++it, ++i )
    {
        if (*it != '0')
        {
            num += 1ULL << i;
        }
    }

    return num;
}

Here's the other helper function.

int getStepsTo1(unsigned long long num)
{
    long int count = 0;
    while (num != 1 )
    {
        if (num % 2 == 0)
            num /= 2;
        else
            num += 1;
        count += 1;
    }
    return count;
}

Working demo: https://ideone.com/yerRfK.

user_4345510
Related