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;

}

CodePudding user response：

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);

CodePudding user response：

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.