The problem is as follows:
//main.cpp - contains solution for finding a wraparound number
#include <iostream>
#include <cassert>
using namespace std;
//ClearBools() initialises an array of bool values all to 0/false.
//The args passed in are the array of bools and the number of elements
//that need initialising to 0.
void ClearBools(bool arrayBools[],int numElems)
{
for(int elem = 0; elem < numElems; elem++)
arrayBools[elem] = 0;
}
//IsDigitVisitedIfNotMark() - this uses an index to check if an element of a bool array
//is true or false. If true return true, if false mark the element as visited and return false
bool IsDigitVisitedIfNotMark(int index,bool digitsVisited[])
{
if(digitsVisited[index] == 1) return true;
digitsVisited[index] = 1;
return false;
}
//FullTested() - This checks if an array of bools has all been set to true yet or not.
//In the context of this program if an array of bools representing the different digits have all been
//visited then they should all be true
bool FullyTested(bool arrayBools[],int numElems)
{
for(int elem = 0; elem < numElems; elem++)
{
if(arrayBools[elem] == 0) return false;
}
return true;
}
//NumDigitsInNumber - simply returns the amount of digits in the passed number
int NumDigitsInNumber(int value)
{
assert(value > 0);
int numDigits = 1;
while(true)
{
//if value divided by 10 is 0, there are no more digits to count
if(value/10 == 0) return numDigits;
//otherwise divide the value by 10, increase the number of recorded digits
//by 1
value /= 10;
numDigits++;
}
}
//PlaceDigitsInArray - This fills in the elements of an integer array with the digits of the number being tested
//e.g if 1234 was passed in, 1 would be stored at element 0 and 4 stored at element 3. Obviously the number
//of digits in the number and the number itself are passed in. The algorithm works backwards by using a
//remainder of the number being divided by 10.
void PlaceDigitsInArray(int digits[],int numOfDigits,int number)
{
//start at the last index
int index = numOfDigits-1;
while(index >= 0)
{
//index the digit by using the remainder and decrement the index
digits[index--] = number % 10;
//divide the number by 10 to place the next digit at the end
number /= 10;
}
}
//IsWrapAround - the main function that does the magic and uses the above functions to come to a result
bool IsWrapAround(int number)
{
//First determine the amount of digits in the number and create arrays to hold the digits in the
//number and a bool array to help 'mark' if that number has been visited yet.
int numOfDigits = NumDigitsInNumber(number);
int* digitsInNumber = new int[numOfDigits];
bool* digitsVisited = new bool[numOfDigits];
//bool array to help check if a digit in the number has already been used, as 1-9 can only be used
//once each
bool digitsUsed[9];
//initialise the bool arrays and put the digits of the number into the int array
ClearBools(digitsVisited,numOfDigits);
ClearBools(digitsUsed,9);
PlaceDigitsInArray(digitsInNumber,numOfDigits,number);
//set the index of the digit to be tested to the first/zeroth position
int index = 0;
while(true)
{
//have all the digits been tested? If so we are done and it is a wraparound number
if(FullyTested(digitsVisited,numOfDigits))
{
delete [] digitsVisited;
delete [] digitsInNumber;
return true;
}
//Check if the current digit has been used/checked already - if it has
//its not a wrap around number
if(IsDigitVisitedIfNotMark(index,digitsVisited))
{
delete [] digitsVisited;
delete [] digitsInNumber;
return false;
}
//get the digit to be tested using the current index
int digitTested = digitsInNumber[index];
//Check if the current digit has been used/checked already - if it has
//its not a wrap around number
if(IsDigitVisitedIfNotMark(digitTested,digitsUsed))
{
delete [] digitsVisited;
delete [] digitsInNumber;
return false;
}
//compute the index of the next digit to be used - add the digit being tested
//to the index and then 'wrap around' if the result is greater than the number
//of digits being tested
index = (index + digitTested)%numOfDigits;
}
}
int main()
{
int value;
cin >> value;
while(true)
{
if(IsWrapAround(value))
cout <<value<<" is a wraparound number"<<endl;
else
cout <<value<<" is not a wraparound number"<<endl;
cin >> value;
}
return 0;
}
I look forward to any suggestions, I found this a fun problem
I like how you checked if the number has been used already before adding it to the vector of digits, and that you mark the numbers in the vector itself as zero as opposed to using any additional storage like I did with my arrays of bools. I might have a crack at implementing your strategy myself later, but without the STL
