ANOOB BACKER Technical Blog: June 2006

C Programming - Divisible By 3 or Not

Given a number we have to find whether it is divisible by 3 or not without using /,%,*.

We are provided with char *itoa(int) function

Please post in your comments. Let us find a good solution!!!!
Solution:
One of the property of a number divisible by 3 is that its sum of digits will be also divisible by 3.
Suppose abcd is a 4 digit decimal number


abdc = 1000a + 100b + 10c + d = (999a + 99b + 9c) + (a + b + c + d)

Here the

999a + 99b + 99c

is divisible by 3. So if

a + b + c + d

is also divisible by three then the number is divisible by three.

Functions:

The most obvious one is


/* returns the remainder */
int mod3(unsigned number)
{
    while (number > 3 ) { number -= 3; }

    number = number == 3 ? 0 : number;
    return number;
}

The same thing modified in a bitwise form will be


int mod3(unsigned number)
{
    const unsigned int s = 2;
    const unsigned int d = (1 << s) - 1;
    unsigned int modulus;

    for (modulus = number; number > d; number = modulus) {
        for (modulus = 0; number; number >>= s) {
            modulus += number & d;
        }
    }
    modulus = modulus == d ? 0 : modulus;
    return modulus;
}

But here are we are provided with atoi so a better solution could be


int mod3(int number)
{
    char *iter;
    char *str = itoa(number);
    while( *(str+1) != '\0' ) {
       number = 0; iter = str;
       while( *iter != '\0' ) {
            number += (*iter - '0');
            iter++;
       }
       str = itoa(number);
    }
    if ( (*str == '3') || (*str == '6') || (*str == '9') )
       return 0;
    return 1;
}

The defect with this function is that if not divisible it will always return 1 rather than the modulus.

Labels: C

Posted by - at 4:04 am | 6 comments read on

C Programming - Remove Characters within a String

The characters to be removed from a string is given as another string.

Your comments are valuable!!

Solution:


void remove(char src[], char del[])
{
     char hash[26] = {0};
     char *fsrc = del,*fdst;
     int count;
     while(*fsrc) {
          hash[*fsrc - 'a'] = 1;
          fsrc++;
     }
     fsrc = fdst = src;
     while(*fsrc) {
          if ( (*fsrc == ' ') || ( hash[*fsrc - 'a'] == 0 ) ) {
               *fdst = *fsrc;
               fdst++;
          }
          fsrc++;
     }
     *fdst = '\0';
}

Labels: C

Posted by - at 10:59 pm | 0 comments read on

C Programming - Rev()

An array of size N has distinct values 1…N in random order. You have only operator called rev(X) (where X is any value from 0 to N-1) which reverses all values from 0 to X (example values 2,3,1,4 and rev(2) gets you 1,3,2,4). Our objective is to sort the array using minimum number of Rev(X) functions. How many permutations of N size array require exactly N number of rev(X) operators to get sorted

a. For size 3 only 1,3,2 requires 3 moves.

This is what I could think off. Do post in your comments!
Solution:


#include < stdio.h >

int elements[] = {1,23,8,3,4,7,8,9,2,1};
int count = sizeof(elements) /sizeof(int);
void rev(int pos)
{
     int iter,swaptemp;
     for(iter=0; iter < pos/2; iter++) {
                 swaptemp = elements[iter];
                 elements[iter] = elements[pos - iter - 1];
                 elements[pos - iter - 1] = swaptemp;
     }
}

int main()
{
    int iter,max=0,pos=0,loop=0;
    for(iter=0; iter < count; iter++) printf("%d ",elements[iter]); printf("\n");
    
    for(loop=count; loop > 0; loop=pos-1) {
       pos=max=0;
       for(iter=0;iter < loop;iter++) {
             if ( elements[iter] > max ) {
                  max = elements[iter];
                  if ( iter > 0 ) {
                       rev(iter);
                       if ( elements[iter+1] < elements[iter] ) {
                            printf("Swapping %d\n",elements[iter+1]);
                            rev(iter+1);
                       }
                       else 
                           continue;
                 }
            }
            pos++;
      }
      rev(pos);
    }
    
    for(iter=0;iter < count;iter++) printf("%d ",elements[iter]); printf("\n");
}

Labels: C

Posted by - at 10:32 pm | 0 comments read on