Number to digits without using strings nor division by 10

Question

So there is this challenge in which you have to write a code which splits a number between 0-999 into digits without using string or division by 10. I've tried so hard and couldn't come up with the perfect algorithm. I got my code working for splitting numbers 1-99 but I really think there's some better alternative without using 111 if statements. Alright, so here's what I got:

#include <iostream>

int main() {
    std::cout << "Enter a number ";
    int number;
    std::cin >> number;

    int cycles;
    if (number > 100) {
        cycles = 3;
    }
    else if (number > 10) {
        cycles = 2;
    }
    else {
        cycles = 1;
    }

    int digit[] = { -1, -1, -1 };
    for (int i = 0; i < cycles; i++) {
        if (number < 10) {
            digit[0] = number;
        }
        else if (number < 100) {
            if (number < 20) {
                digit[1] = number - 10;
                number = 1;
            }
            else if (number < 30) {
                digit[1] = number - 20;
                number = 2;
            }
            else if (number < 40) {
                digit[1] = number - 30;
                number = 3;
            }
            else if (number < 50) {
                digit[1] = number - 40;
                number = 4;
            }
            else if (number < 60) {
                digit[1] = number - 50;
                number = 5;
            }
            else if (number < 70) {
                digit[1] = number - 60;
                number = 6;
            }
            else if (number < 80) {
                digit[1] = number - 70;
                number = 7;
            }
            else if (number < 90) {
                digit[1] = number - 80;
                number = 8;
            }
            else {
                digit[1] = number - 90;
                number = 9;
            }
        }
        else if (number < 1000) {
            if (number < 200) {
                number -= 100;
            }
            else if (number < 300) {
                number -= 200;
            }
            else if (number < 400) {
                number -= 300;
            }
            else if (number < 500) {
                number -= 400;
            }
            else if (number < 600) {
                number -= 500;
            }
            else if (number < 700) {
                number -= 600;
            }
            else if (number < 800) {
                number -= 700;
            }
            else if (number < 900) {
                number -= 800;
            }
            else {
                number -= 900;
            }
        }
    }

    for (int i = 0; i < 3; i++) {
        if (digit[i] != -1) {
            std::cout << digit[i] << " ";
        }
    }
    std::cout << "\n";

    std::cout << "Press any key to exit... ";
    char i;
    std::cin >> i;
    return 0;
}

I'm stuck, so if anyone will be able to help me, that will be much appreciated!

I'm afraid not. Just pure algebra with the numbers without division by 10. — user3426112, Oct 18 '15 at 21:03
@user3426112 *So there is this challenge in which you have to write a code* Aren't you supposed to formulate a solution *first* before writing one line of code? It makes little sense to write code for something you haven't really solved (on paper). — PaulMcKenzie, Oct 18 '15 at 21:38

score 3 · Accepted Answer · answered Oct 18 '15 at 21:41

Basically the problem comes down to, how to implement the division operator without using division operator. As there are quite limited possibilities, i.e, when testing for each digit there are only 10 possible outcomes 0-9, a simple solution is to go through all of them. You could just use multiplication for each, but a slightly faster one is to iterate over the possible answers. So a simple function which takes base (1,10 or 100) and the number you are splitting in parts would be

int getDigit(int base, int number) {
  int digit = 0;
  for (int i = base;i <= number;i += base) ++digit;
  return digit;
}

This function works only if number < 10*base. So you need to start from the largest digit. Then subtract base*digit from the number and repeat until you have gone over all the digits.

wrangler · Answer 2 · 2015-10-18T21:59:16.183

Since you cant divide by 10 you could use shift operators equivalent to division by 10 see here:

For division by 10 using shift operators:

A:our integer Q:quotient

Q = ((A >>  1) + A) >> 1; 
Q = ((Q >>  4) + Q)     ; 
Q = ((Q >>  8) + Q)     ; 
Q = ((Q >> 16) + Q) >> 3; 
/* either Q = A/10 or Q+1 = A/10 for all 32-bit unsigned A */

For remainder:

R=A-10*Q;

We could expand this method for our purpose using while loop and since we know our integer is less than 999 we could take an array[3]:

#include<stdio.h>
#include<stdlib.h> 
int main()
{
    int A=123;
    int R=A;
    int Q=123; /* the quotient */

    Q = ((A >>  1) + A) >> 1;

    int ar[3]={0},i=2;

    //loop for getting all digits
    while(Q>10)
    {
       Q = ((Q >>  4) + Q)     ;
       Q = ((Q >>  8) + Q)     ;
       Q = ((Q >> 16) + Q) >> 3;
       //storing ramainder in array in reverse
       ar[i--]=R-10*Q;
       R=Q;
    }
    ar[i]=Q;
    for(i=0;i<3;i++)
      printf("%d ",ar[i]);
    return 0; 
}

Tyler Moore · Answer 3 · 2015-10-18T22:20:21.993

2

Use two loops, one that iterates through place holders from highest to lowest and an inner loop that subtracts from the value until the value is less than that place, effectively dividing without using the division operator. Something like:

int number;
int subtractionvalue;
int[3] placevalues;
for(int thisvalue=2;thisvalue>=0;thisvalue--){
    subtractionvalue=round(pow((double)10,thisvalue));
    while(number>=subtractionvalue){
        number=number-subtractionvalue;
        placevalues[thisvalue]++;
    }
}

The placevalues array will contain your solution.

edited Oct 18 '15 at 22:20

answered Oct 18 '15 at 22:07

Tyler Moore

83
6

2

`pow(10,thisvalue);` Surprise, surprise: http://stackoverflow.com/questions/25678481/why-pown-2-return-24-when-n-5/25678721#25678721 – PaulMcKenzie Oct 18 '15 at 22:10
@PaulMcKenzie thanks. That's what I get for stack exchanging on my phone. – Tyler Moore Oct 18 '15 at 22:21

kesse · Answer 4 · 2015-10-18T22:15:58.887

I may be missing the point, and bare with my C#, but wouldn't counting bee the easiest?

static void Main(string[] args)
{
  int number = 592;
  int digit1 = 0;
  int digit2 = 0;
  int digit3 = 0;
  for (int c = 0; c < number; c++)
  {
    digit1 += 1;
    if (digit1 == 10)
    {
      digit2 += 1;
      digit1 = 0;
    }
    if(digit2 == 10)
    {
      digit3 += 1;
      digit2 = 0;
    }
  }
  Console.WriteLine(digit1);
  Console.WriteLine(digit2);
  Console.WriteLine(digit3);
}

C++ version:

int main()
{
  std::cout << "Enter a number ";
  int number;
  std::cin >> number;
  int digit1 = -1;
  int digit2 = -1;
  int digit3 = -1;
  for (int c = 0; c < number; c++)
  {
    digit1 += 1;
    if (digit1 == 10)
    {
      digit2 += 1;
      digit1 = 0;
    }
    if (digit2 == 10)
    {
      digit3 += 1;
      digit2 = 0;
    }
  }
  if (digit3 > -1) {
    std::cout << digit3+1 << " ";
  }
  if (digit2 > -1) {
    std::cout << digit2+1 << " ";
  }
  if (digit1 > -1) {
    std::cout << digit1+1 << " ";
  }
  std::cout << "\n";

  std::cout << "Press any key to exit... ";
  char i;
  std::cin >> i;
  return 0;
}

So if the number is "6", your solution would write "006". I don't think that is what the OP is after. Anyway, even if your solution would work, it's in C#, not C++. — PaulMcKenzie, Oct 18 '15 at 21:54
Perhaps not. I guess starting each digit at -1 and only printing if over -1 would solve that. — kesse, Oct 18 '15 at 21:57
So many different ways to solve this problem, just wow! Thank you very much! :) — user3426112, Oct 19 '15 at 04:09

score 1 · Answer 5 · answered Oct 18 '15 at 22:49

One approach is to convert the integer into a fixed-point format that provides for an integer portion able to hold one decimal digit, and using the remaining bits for the fractional part. For example when using 32-bit int, we can allocate the 4 most significant bits for the integer, and the 28 least significant bits for the fraction.

The original number is first converted into a pure fraction, in this case by dividing by 1000. It is then multiplied by the scale factor, 2²⁸. For simplicity the code below uses floating-point arithmetic for this computation, however this can also be done using integer arithmetic if need be. Since conversion of floating-point to integer types is truncating in C++, ceil() is used to bump up the fixed-point number very slightly.

Once we have converted to fixed-point format, we can now extract each decimal digit by multiplying the fixed-point number with 10, extracting the integer portion of the product as the next decimal digit, then discarding the integer portion of the fixed-point result.

I retained as much of the original code as possible for the program below.

#include <iostream>
#include <cmath>

int main() {
    std::cout << "Enter a number ";
    int number;
    std::cin >> number;
    int digit[] = { -1, -1, -1 };

    unsigned int t, dec_digit;
    bool have_seen_nonzero;

    t = ceil (number / 1e3 * (1 << 28)); // 4.28 fixed-point representation
    for (int pos = 0; pos < 3; pos++) {
        t = t * 10;            
        dec_digit = t >> 28; // extract integer portion of fixed-point number
        t = t & 0x0fffffff; // discard integer portion of fixed-point number
        have_seen_nonzero = dec_digit != 0;
        if (have_seen_nonzero) digit[pos] = dec_digit;
    }

    for (int i = 0; i < 3; i++) {
        if (digit[i] != -1) {
            std::cout << digit[i] << " ";
        }
    }
    std::cout << "\n";

    std::cout << "Press any key to exit... ";
    char i;
    std::cin >> i;
    return 0;
}

Number to digits without using strings nor division by 10

5 Answers5