CODEWITHSUNDEEP
c++algorithmmathoperator-overloadingsubtraction
Matt Thompson
Matt Thompson

Reputation: 35

Decremeting one from a number represent as a vector?

I am trying to decrement a number, which can be infinitely long and is represented in a vector, by 1. As a small example:

vector<int> v1 = {5, 0, 0, 0};

After subtracting one from the end, the result should be:

vector<int> v1 = {4, 9, 9, 9};

This is my current code:

int size = v1.size();
bool carry = false;

for (int i = size - 1; i > 0; i--) {
    if (v1.at(i) == 0) {
        v1.at(i) = 9;

        if (v1.at(0) == 1) {
            v1.at(0) = 0;
        }

        carry = true;
    } else {
        v1.at(i) -= 1;
        carry = false;
    }
}

if (carry == true && v1.at(0) == 0) {
    v1.erase(v1.begin());
} else if (carry == true) {
    v1.at(0) -= 1;
}

return v1;

When I test it, everything works fine, except numbers like 11119. They turn out to be 00019. Is there anything I could tweak?

Upvotes: 0

Views: 58

Answers (2)

Jacob Schultz Andersen
Jacob Schultz Andersen

Reputation: 9

A subtraction as you tried to do, could be done like this:

#include <iterator>

std::vector<int> v1 = {5, 0, 0, 0};

for (std::vector<int>::reverse_iterator i = v1.rbegin(); i != v1.rend(); i++) {
    *i -= 1;
    if (*i < 0) {
      *i = 9;
    }
    else {
      break;
    }
}

Upvotes: 0

R Sahu
R Sahu

Reputation: 206627

It seems to me that you didn't think through the logic clearly.

Here's what needs to happen.

If the last number is 0, it needs to be changed to 9 and a carry has to be maintained.
Repeat until no carry needs to be maintained.

That logic is best implemented using a do - while loop. Here's what I came up with.

int size = v.size();
bool carry = true;
int i = size - 1;
do
{
   if (v.at(i) == 0)
   {
      v.at(i) = 9;
   }
   else
   {
      v.at(i)--;
      carry = false;
   }
   --i;
}
while ( carry == true && i >= 0);

Here's a complete program

#include <iostream>
#include <vector>

void test(std::vector<int> v)
{
   int size = v.size();
   bool carry = true;
   int i = size - 1;
   do
   {
      if (v.at(i) == 0)
      {
         v.at(i) = 9;
      }
      else
      {
         v.at(i)--;
         carry = false;
      }
      --i;
   }
   while ( carry == true && i >= 0);

   for ( auto item : v )
   {
      std::cout << item << " ";
   }
   std::cout << std::endl;
}

int main()
{
   test({1, 1, 1, 1, 9});
   test({5, 0, 0, 0, 0});
}

and its output

1 1 1 1 8
4 9 9 9 9

See it working at https://ideone.com/lxs1vz.

Upvotes: 1

Related Questions