For this project you will be designing and implementing a system, in either C or

Question

For this project you will be designing and implementing a system, in either C or C++, to answer a few mathematical questions. First, given the number 123456789, is it possible to find a permutation (i.e. a rearrangement that preserves the count of each number) such that the left most digit is evenly divisible by 1, the two left most digits are evenly divisible by 2, the three left most digits are divisibly by 3 and so on? For example, in 123456789, 1 is evenly divisible by 1, 12 is evenly divisible by 2, 123 is evenly divisible by 3, but because 1234 is not evenly divisible by 4 this number is not a solution to the question. Second, is it possible to find a similar permutation given the number 1234567890? Finally, is it possible to find a similar permutation for any of the given hexadecimal numbers, 1234567890AB, 1234567890ABC, 1234567890ABCD, 1234567890ABCDE, 1234567890ABCDEF?

Implementation
Your program must provide the following functionality and adhere to the following constraints:
Your program should output
o The count of the possible solutions for 1,2,3,4,5,6, and 7 digit numbers using the digits 1-9
Example: For a 1 digit number there are 9 possible solutions
o All possible solutions for 8 and 9 digit numbers in decimal format using the digits 1-9
o All possible solutions for 10 digit numbers in decimal format using the digits 0-9
o All possible solutions for 11,12,13,14,15, and 16 digit numbers in hexadecimal format using the digits 0-F
No digit can be used more than once per number
All output should be outputted to the terminal
You may not hardcode the solutions to these questions into your program. The solution must be determined as a result of your program checking numbers
Your program should complete and output all solutions in 5 minutes or less of real time, according to Linux’s time program, while running on the CSE machines. You can use this program by adding time in front of your program call, e.g. time ./a.out
Your code must be well commented.
You must provide a short README file which includes your name and explains how to compile and run your program.
Additionally, you may write a makefile if you want your code to compile with additional flags.

Explanation / Answer

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <conio.h>

#include <math.h>

long int number,pow1,arr[3],counter=0;

int n,flag=-1;

// Function to swap values at two pointers

void swap(char *x, char *y)

{

char temp;

temp = *x;

*x = *y;

*y = temp;

}

// Function to calculate permutations of string

void permute(char *a, int l, int r)

{

int i,j,k,size;

if (l == r){

number = atoi(a); //Converting String into Number

//Storing Values of Number in arr to Divide it later like 1,12,123,,1234,....

for(k=n-1,j=0;k>=0,j<=n-1;j++,k--){

pow1=pow(10,k);

arr[j]=number/pow1;

}

//Checking if Number stored in arr are divisible like 1/1,12/2,123/3

for(j=0;j<n;j++){

if(arr[j]%(j+1)==0)

flag=1;

else{

flag=0;

break;

}

//If the all the numbers are divisible then counter increase and we print this permutation as it is possible

}

if(flag==1){

counter++;

printf("Permutation Divisor ");

for(j=0;j<n;j++)

printf("%ld %d ",arr[j],j+1);

}

}

else

{

for (i = l; i <= r; i++)

{

swap((a+l), (a+i));

permute(a, l+1, r);

swap((a+l), (a+i)); //backtrack

}

}

}

/* Driver program to test above functions */

int main()

{

char str[] = "123456789";

n = strlen(str);

clrscr();

permute(str, 0, n-1);

printf("Number of possible permutations are %ld",counter);

getch();

return 0;

}

You can use this code to calculate outcomes for a string of length max 9 and that too from 1-9. As for 0-9 and hexadecimal, it is more complicated and would require more time to solve. But with the help of this code, you will find it easy to make the other two possible.

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.