CODEWITHSUNDEEP
c++algorithminteger
George
George

Reputation: 3943

C++: Break the digits of an integer into equal parts

So I have a problem at hand and would like to know the most efficient way to go about it.

I would like to break down a integer into part, so say I have 1234 I would like to break it into 12 and 34 or if I have 123 I would like it to be 1 and 23.

My original idea is to convert to string as I would in some modern programming language, then get the length of the string and then the substring, but I do not feel this is a good way to do it in C++.

Please I would like suggestions on how to go about solving this issue, I already have a function that would help me get the number of digits from an integer.

template <class T> int getDigits(T number) {
int digits = 0;
while(number ){
    number /= 10;
    digits++;
}
    return digits;
}

Upvotes: 3

Views: 1355

Answers (5)

tu4n
tu4n

Reputation: 4450

Getting total number of digits: 

int n = 1;
if (the_integer != 0)
    n = floor(log10(abs(the_integer))) + 1;

The right number will always have n-n/2 digits, the required numbers can be calculated as follow: 

int rDigits = n-n/2;
int factor = pow(10, rDigits);
int left = the_integer / factor;
int right = the_integer % factor;

Take care of type conversion when using pow in c++

Total Complexity: O(1)
Actually log-function have O(n) complexity but its ALOT faster under the hood

Upvotes: 2

Biruk Abebe
Biruk Abebe

Reputation: 2233

int digit=..;//the number of digits in the number,you already have this
int number=...;//you have the number
int half_way=static_cast<int>(::ceil(digit/2.0));//getting the largest number of digits that will be in the parts
int count=0;

int part_numbers[2]={0};//the two parts

while(number>0)
{
    int part=0;
    for(int j=0;j<half_way;j++)
    {
      part+=static_cast<int>(pow(10.0,j) * (number% 10));
      number=number/10;
    }
    part_numbers[count]=part;
    count++;
}

And as pointed out by anatolyg in the comment section you can use a custom integer exponentiation as given here

Upvotes: 0

anatolyg
anatolyg

Reputation: 28251

The answer by Deus Sum uses the following idea:

  1. Calculate how many digits there are in each part
  2. Calculate the corresponding power of 10
  3. Divide the number by the power of 10; the quotient and remainder are your parts

Instead of doing (1) and (2) separately, the two numbers can be calculated in the same loop. To do that, in addition to increasing a counter each time, multiply a temporary variable by 10 every other time.

template <class T> void PrintHalves(T number)
{
    int digits = 0;
    T pow10 = 1;
    T temp = number;
    while (temp != 0)
    {
        temp /= 10;
        if (digits % 2 == 0)
            pow10 *= 10;
        digits++;
    }
    // pow10 is a power of 10 that is close to sqrt(number)
    T high = number / pow10;
    int high_digits = digits / 2; // number of digits in the high part
    T low = number % pow10;
    int low_digits = digits - high_digits; // number of digits in the low part
    std::cout <<
        std::setw(high_digits) << std::setfill('0') << high << ' ' <<
        std::setw(low_digits) << std::setfill('0') << low << '\n';
}

In the code, I used the setw and setfill manipulators to print the correct number of leading zeros.

Note: for single-digit numbers (including 0), the separation of the digits is messy - the high part is empty, so it prints a zero instead.

Upvotes: 1

fjardon
fjardon

Reputation: 7996

You almost have all the needed code. Just remark that your digits variable in your function represents the current power of ten of the right part of the number's string representation. Just stop when this is more than the left part.

void split_int(unsigned long long a, unsigned long long& part1, unsigned long long& part2)
{
  part1 = a;
  part2 = 0;
  unsigned long long power = 1;

  while(part1 >= power) {
    unsigned long long r = part1%10;

    part1 /= 10;
    part2 += r*power;

    power *= 10;   
  }
}

With the following test program

int main() {
  unsigned long long x;
  unsigned long long p1, p2;

  x = 1234u;
  split_int(x, p1, p2);
  std::cout << "x = " << x << " -> " << p1 << " " << p2 << std::endl;

  x = 123u;
  split_int(x, p1, p2);
  std::cout << "x = " << x << " -> " << p1 << " " << p2 << std::endl;

  x = 9876543210u;
  split_int(x, p1, p2);
  std::cout << "x = " << x << " -> " << p1 << " " << p2 << std::endl;  
}

It will print:

x = 1234 -> 12 34
x = 123 -> 1 23
x = 9876543210 -> 98765 43210

Upvotes: 2

Deus Sum
Deus Sum

Reputation: 156

Here's a simple implementation of the algorithm:

template <typename T>
std::pair<T, T> seperateNum(T num) {
    auto num_digits = getDigits(num);
    auto half_digits = (num_digits % 2 == 0) ? num_digits / 2 : (num_digits / 2) + 1;

    auto mult = static_cast<T>(pow(10, half_digits));

    return {num / mult, num % mult};
}

Only works for integer types, of course.

Upvotes: 1

Related Questions