Get this book -> Problems on Array: For Interviews and Competitive Programming

## In this article, we will go through different ways to divide by 3 in C++ Standard Template Library (STL) and general software techniques. Methods used to divide number by 3 are:

- Solution using a basic method
- Solution using fma() library function, works for any positive number
- A logarithmic solution
- Solution using iterative way
- Using Bitwise operator
- Using File
- Using div() function from standard library
- Using counters is a basic solution
- Using itoa() function

We will dive into each method in depth.

### 1. Solution using a basic method:

Here we use a simple way of finding divisbility by 3. What we doing here is decrementing the number by 3 and then checking whether it is greater than 3 or not simultaneously after every loop we are increasing the quotient (i.e. result, here). Hence when the loop reaches the number less than or equal to 3, we will finally get the final increment in result and which wil be out required output.

```
int div3(int x)
{
int reminder = abs(x);
int result = 0;
while(reminder >= 3)
{
result++;
reminder--;
reminder--;
reminder--;
}
return result;
}
int main()
{
cout<<"Provide the no.";
cin>>x;
div3(x);
return 0;
}
```

### 2. Solution using fma() library function, works for any positive number:

The fma() function takes three arguments a, b and c, and returns (ab)+c without losing precision. The fma() function is defined in the cmath header file. Here we use a method in which we multiply 3 with 1 and add it by 3 until we reach the provided number. Simultaneously we increment the result after every loop. Hence when loop reaches equal or upto number we get our final quotient as our result.

```
#include <bits/stdc++.h>
#include <stdio.h>
#include <math.h>
using namespace std;
int main()
{
int number = 8;//Any +ve no.
int temp = 3, result = 0;
while(temp <= number){
temp = fma(temp, 1, 3); //fma(a, b, c) is a library function and returns (a*b) + c.
result = fma(result, 1, 1);
}
cout<<"\n\n"<<number<<"divided by 3 =\n"<<result;
}
```

### 3. A logarithmic solution to this would be:

In mathematics a way to find quotient of number divide by 3 is using logarithmic formula i.e. log(pow(exp(numerator),pow(denominator,-1))).

So here we simply apply the logaritmic formula log(pow(exp(number),0.33333333333333333333)) by including <math.h> header file.

```
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int main()
{
cout<<"Provide number";
cin>>number;
int result=log(pow(exp(number),0.33333333333333333333))
cout<<result;
}
```

### 4. Solution using iterative way:

Using for loop iteration, We will iterate the variable till 3 then will check with the provided number whether it is less than the provided number, we will increment gResult each time. Once we reach the number we will get our quotient as gResult as our required output.

```
#include <bits/stdc++.h>
#include <stdio.h>
#include <math.h>
using namespace std;
int main()
{
int aNumber = 500;
int gResult = 0;
int aLoop = 0;
int i = 0;
for(i = 0; i < aNumber; i++)
{
if(aLoop == 3)
{
gResult++;
aLoop = 0;
}
aLoop++;
}
cout<<"Result of" aNumber/ 3 <<"="<< gResult;
return 0;
}
```

### 5. Using Bitwise operator:

Here the function performs the same sum function, but it requires the + operator, so all you have left to do is to add the values with bit-operators. The left-shift and right-shift operators are equivalent to multiplication and division by 2 respectively.

```
// replaces the + operator
int add(int x, int y)
{
while (x) {
int t = (x & y) << 1;
y ^= x;
x = t;
}
return y;
}
int divideby3(int num)
{
int sum = 0;
while (num > 3) {
sum = add(num >> 2, sum);
num = add(num >> 2, num & 3);
}
if (num == 3)
sum = add(sum, 1);
return sum;
}
```

### 6. Using File:

In this method we applied mathematical formulae of divison by creating file.

The 'fwrite' writes number bytes (number being 123456 in the example above).

The 'rewind' resets the file pointer to the front of the file.

The 'fread' reads a maximum of number "records" that are divisor in length from the file, and returns the number of elements it read.

If you write 30 bytes then read back the file in units of 3, you get 10 "units". i.e. 30 / 3 = 10.

```
#include <bits/stdc++.h>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
int main()
{
FILE * fp=fopen("temp.dat","w+b");
int number=12346;
int divisor=3;
char * buf = calloc(number,1);
fwrite(buf,number,1,fp);
rewind(fp);
int result=fread(buf,divisor,number,fp);
printf("%d / %d = %d", number, divisor, result);
free(buf);
fclose(fp);
return 0;
}
```

### 7. Using div() function from standard library:

Here we used standard div() function from standard library. It returns the integral quotient and remainder of the division of number by denom ( number/denom ) as a structure of type div_t, ldiv_t or lldiv_t, which has two members: quot and rem.

```
#include <bits/stdc++.h>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
int main(int argc, char *argv[])
{
int num = 1234567;
int den = 3;
div_t r = div(num,den); // div() is a standard C++ function.
cout<<r.quot;
return 0;
}
```

### 8. Using counters is a basic solution:

Here first the number is equated after every increment . Simultaneoulsy, after every third check we increment result till we reach the number. Hence we will get result as our quotient and also our required output.

```
int DivBy3(int num) {
int result = 0;
int counter = 0;
while (1) {
if (num == counter) //Modulus 0
return result;
counter = abs(~counter); //++counter
if (num == counter) //Modulus 1
return result;
counter = abs(~counter); //++counter
if (num == counter) //Modulus 2
return result;
counter = abs(~counter); //++counter
result = abs(~result); //++result
}
}
```

### 9.Using itoa() function:

itoa() is a standard C++ function. itoa function converts integer into null-terminated string. Here, using itoa to convert to a base 3 string. Drop the last trit and convert back to base 10.

```
int div3(int i) {
char str[42];
sprintf(str, "%d", INT_MIN); // Put minus sign at str[0]
if (i>0) // Remove sign if positive
str[0] = ' ';
itoa(abs(i), &str[1], 3); // Put ternary absolute value starting at str[1]
str[strlen(&str[1])] = '\0'; // Drop last digit
return strtol(str, NULL, 3); // Read back result
}
```

All the ways discussed above implements **different ways to divide by 3** in C++ Standard Template Library.