### EncodeArray Problem - I'm lost on this one

Hi guys, I have this question, I am completely lost on how to go about this. kindly help even if it is just the algorithm or pseudocode.
I wouldn't mind If you decide to come up with a solution though.

An integer number can be encoded as an array as follows. Each digit n of the number is represented by n zeros followed by a 1. So the digit 5 is represented by 0, 0, 0, 0, 0, 1. The encodings of each digit of a number are combined to form the encoding of the number. So the number 1234 is encoded as the array {0,1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1}. The first 0, 1 is contributed by the digit 1, the next 0, 0, 1 is contributed
by the digit 2, and so on. There is one other encoding rule: if the number is negative, the first element of the
encoded array must be -1, so -201 is encoded as {-1, 0, 0, 1, 1, 0, 1}. Note that the 0 digit is represented by
no zeros, i.e. there are two consecutive ones!
Write a function named encodeArray that takes an integer as an argument and returns the encoded array. the function prototype is
int * encodeArray(int n)

Hints
Use modulo 10 arithmetic to get digits of number
Make one pass through the digits of the number to compute the size of the encoded array.
Make a second pass through the digits of the number to set elements of the encoded array to 1.

 Make one pass through the digits of the number to compute the size of the encoded array.

 12345678 int* encodeArray(int n) { // one pass that prints each digit of n separately // print required size of the array return nullptr; }
There is one very significant issue with the prototype for that function.
 There is one very significant issue with the prototype for that function.

No way to return the length of the array? :-)
One solution is to mark the end, perhaps with the number 2.
It would still technically follow the instructions since they don't explicitly disallow it.
Last edited on
Yes, that was it, @dutch. No way of doing much with the array unless you knew its allocated length.

The only options I could come up with were changing the prototype so that one argument was a reference that gave the size, or letting the first element of the array hold the length.

Actually, I quite like your idea, which is a bit like null-terminating c-strings.
Last edited on
I didn't think about putting the length in the first element. That's a good idea, too. So there are three options, and one of them must be used or, as you said, the encoded array is pretty much useless.
This is a horrible code, due to the constraints of the specifications. This is to provide an idea of one way (out of many).

 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168 #include #include // For abs function. int* encodeArray(int); int* positiveNum(int, int&); int* negativeNum(int, int&); int arraySize(int); void printArray(int*, int); int main() { int num{}; std::cout << "Enter an integer to encode it: "; std::cin >> num; int *pArray {encodeArray(num)}; // Deallocate the memory that was allocated under // the positiveNum function or negativeNum function (depending // on the user's input of the integer number. The positiveNum or // negativeNum function will be called from the encodeArray function. delete [] pArray; pArray = nullptr; } int* encodeArray(int num) { int *arrNum {nullptr}; int size{}; if (num > 0) { arrNum = positiveNum(num, size); } // If the number is negative, then go to the negativeNum function, // which will allocate one more element in the array to hold the number // -1 into the first element in the array. else if (num < 0) { arrNum = negativeNum(std::abs(num), size); // Use the abs function to change from neg to pos number. } printArray(arrNum, size); return arrNum; // Returns the pointer to the dynamically allocated array. } int arraySize(int num) { // Make one pass through the digits of the number // to compute the size of the encoded array. int countNumDigits{ 0 }; int runningTotal{ 0 }; int absoluteNum {std::abs(num)}; while (absoluteNum > 0) { int digit = absoluteNum % 10; // Use the modulus operator to determine a single digit. absoluteNum /= 10; // Obtain the other digits to the left of the single digit. runningTotal += digit; // Add the single digits (i.e. 1234 would equal 10). countNumDigits++; // Keep the count of the number of digits (i.e. 123 would count 3). } const int size{ runningTotal + countNumDigits }; // Determine the size of the array. return size; } int* positiveNum(int num, int& size) { size = arraySize(num); // Save the size of the array. // Dynamically allocate the array with the size // determined by the function arraySize. int *arrNum = nullptr; arrNum = new int[size]; // Set index of the encoded array to 1. for (int count = 0; count < size; count++) arrNum[count] = 1; int index{ size - 1 }; // Save the last index from the array. while (num > 0) { int digit = num % 10; // Use the modulus operator to determine a single digit. num /= 10; // Obtain the other digits to the left of the single digit. // Get the difference between the index and the single // digit extracted to place the 0s (i.e. if the digit is 2, // then the array would be like 0, 0, 2. int diffMaxandMinElem{ index - digit }; // Traverse the array from the last index to place the 0s in // front of the array element. For example, the number 20103 would // be 0,0,1,1,0,1,1,0,0,0,1. for (int count = index - 1; count >= diffMaxandMinElem || digit == 0; count--) { // If the digit is 0, then break out of loop // to go to the next index of the array. if (digit == 0) { index = count; break; } else { arrNum[count] = 0; index = count - 1; } } } return arrNum; // Returns the pointer to the dynamically allocated array. } int* negativeNum(int num, int& size) { size = arraySize(num) + 1; // Additional element to define the first element as -1 int *arrNum = nullptr; arrNum = new int[size]; arrNum[0] = -1; // The first element must be -1 for negative numbers. // Set index of the encoded array from the second element to 1. for (int count = 1; count < size; count++) arrNum[count] = 1; int index{ size - 1 }; // Save the last index from the array. while (num > 0) { int digit = num % 10; num /= 10; int diffMaxandMinElem{ index - digit }; for (int count = index - 1; count >= diffMaxandMinElem || digit == 0; count--) { if (digit == 0) { index = count; break; } else { arrNum[count] = 0; index = count - 1; } } } return arrNum; // Returns the pointer to the dynamically allocated array. } void printArray(int* arrNum, int size) { std::cout << "{ "; for (int count = 0; count < size; count++) std::cout << arrNum[count] << " "; std::cout << "}\n"; }
Last edited on
 There is one very significant issue with the prototype for that function.

Yes, but since this is clearly homework, the teacher could have intentional nefarious scheme.

Overall, we can ask whether one should code strictly to specification, deviate from it, or report the issues in specification?
@Chicofeo, can you print the array from OUTSIDE the function that creates it; e.g. from main()? If the array isn't usable outside the function there wouldn't be much point in returning it.

@keskiverto, I tried it and decided to change the prototype. Personally, I would have gone for "report the issues in specification". I can't believe that teachers would ever have ... "intentional nefarious schemes". Heaven forbid!!!

Last edited on
@lastchance, I concur with the usability issue. I modified due to unnecessary duplication on my first draft.
 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140 #include #include // For abs function. int* encodeArray(int); int arraySize(int); void printArray(int*, int); int main() { int num{}; std::cout << "Enter an integer to encode it: "; std::cin >> num; const int size{ arraySize(num) }; int *pArray {encodeArray(num)}; printArray(pArray, size); //Or std::cout << "{ "; for (int count = 0; count < size; count++) std::cout << pArray[count] << " "; std::cout << "}\n"; // Deallocate the memory that was allocated under // the positiveNum function or negativeNum function (depending // on the user's input of the integer number. The positiveNum or // negativeNum function will be called from the encodeArray function. delete [] pArray; pArray = nullptr; } int* encodeArray(int num) { const int size{arraySize(num)}; int absoluteValue {std::abs(num)}; // Dynamically allocate the array with the size // determined by the function arraySize. int *arrNum = nullptr; arrNum = new int[size]; if (num < 0) // If the number is negative, an extra element is allocated { arrNum[0] = -1; // The first element must be -1 for negative numbers. // Set index of the encoded array from the second element to 1. for (int count = 1; count < size; count++) arrNum[count] = 1; } else { // Set index of the encoded array to 1. for (int count = 0; count < size; count++) arrNum[count] = 1; } int index{ size - 1 }; // Save the last index from the array. while (absoluteValue > 0) { int digit = absoluteValue % 10; // Use the modulus operator to determine a single digit. absoluteValue /= 10; // Obtain the other digits to the left of the single digit. // Get the difference between the index and the single // digit extracted to place the 0s (i.e. if the digit is 2, // then the array would be like 0, 0, 2. int diffMaxandMinElem{ index - digit }; // Traverse the array from the last index to place the 0s in // front of the array element. For example, the number 20103 would // be 0,0,1,1,0,1,1,0,0,0,1. for (int count = index - 1; count >= diffMaxandMinElem || digit == 0; count--) { // If the digit is 0, then break out of loop // to go to the next index of the array. if (digit == 0) { index = count; break; } else { arrNum[count] = 0; index = count - 1; } } } return arrNum; // Returns the pointer to the dynamically allocated array. } int arraySize(int num) { // Make one pass through the digits of the number // to compute the size of the encoded array. int countNumDigits{ 0 }; int runningTotal{ 0 }; int absoluteNum {std::abs(num)}; int size{ 0 }; while (absoluteNum > 0) { int digit = absoluteNum % 10; // Use the modulus operator to determine a single digit. absoluteNum /= 10; // Obtain the other digits to the left of the single digit. runningTotal += digit; // Add the single digits (i.e. 1234 would equal 10). countNumDigits++; // Keep the count of the number of digits (i.e. 123 would count 3). } // If the num inputted by the user is positive if (num > 0) { size = runningTotal + countNumDigits; } else// An extra array element to place the -1 as the first element. { size = (runningTotal + countNumDigits) + 1; } return size; } void printArray(int* arrNum, int size) { std::cout << "{ "; for (int count = 0; count < size; count++) std::cout << arrNum[count] << " "; std::cout <<"}\n"; }
Last edited on
Here's a couple of unconventional ways. Neither meet the exact specifications of the assignment.

 123456789101112131415161718192021222324252627282930313233343536 #include #include #include using namespace std; int *encodeArray( int n, int &size ) { string nstring = to_string( abs( n ) ); // Original number as a string string s; // New array as a string for ( char c : nstring ) s += string( c - '0', '0' ) + '1'; size = s.size() + ( n < 0 ); // int array size int *result = new int[size]; int p = 0; if ( n < 0 ) result[p++] = -1; for ( char c : s ) result[p++] = c - '0'; return result; } //========================================================== int main() { int tests[] = { -201, -5, 0, 5, 1234 }; int size; for ( int n : tests ) { int *code = encodeArray( n, size ); cout << n << ": "; for ( int i = 0; i < size; i++ ) cout << code[i]; cout << '\n'; delete [] code; } }

 123456789101112131415161718192021222324252627282930313233343536373839404142434445 #include #include using namespace std; int *encodeArray( int n, int &size ) { // First pass gets array size int nn = abs( n ); size = ( n < 0 ); do { size += nn % 10 + 1; nn /= 10; } while( nn ); int *result = new int[size]; // Second pass assigns digits nn = abs( n ); int pos = size - 1; do { result[pos--] = 1; for ( int i = nn % 10; i; i-- ) result[pos--] = 0; nn /= 10; } while( nn ); if ( n < 0 ) result[pos] = -1; return result; } //========================================================== int main() { int tests[] = { -201, -5, 0, 5, 1234 }; int size; for ( int n : tests ) { int *code = encodeArray( n, size ); cout << n << ": "; for ( int i = 0; i < size; i++ ) cout << code[i]; cout << '\n'; delete [] code; } }

 -201: -1001101 -5: -1000001 0: 1 5: 000001 1234: 01001000100001
Nice one! But if you're modifying the prototype, you may as well go all the way and return a vector.

 1234567891011121314151617181920212223242526 #include #include #include auto encodeNumber(int n) { std::vector code; if (n < 0) code.push_back(-1); for (char c: std::to_string(std::abs(n))) { code.insert(code.end(), c - '0', 0); code.push_back(1); } return code; } int main() { for (int n: {-201, -5, 0, 5, 1234}) { auto code = encodeNumber(n); std::cout << n << ": "; for (int i: code) std::cout << i; std::cout << '\n'; } }
Nice too! Actually, I might just as well have returned the string!

 1234567891011121314151617 #include #include #include using namespace std; string encode( int n ) { string s; for ( char c : to_string( abs( n ) ) ) s += string( c - '0', '0' ) + '1'; return n < 0 ? "-1" + s : s; } int main() { int tests[] = { -201, -5, 0, 5, 1234 }; for ( int n : tests ) cout << n << ": " << encode( n ) << '\n'; }

Last edited on
Arrgghhh! Didn't think of that!
Alternatively, use the "2 at the end" trick to stick to the given prototype.

 12345678910111213141516171819202122232425262728293031 #include #include int* encodeArray(int n) { auto ns = std::to_string(std::abs(n)); int size = (n < 0); for (auto c: ns) size += c - '0' + 1; auto code = new int[size + 1]; auto p = code; if (n < 0) *p++ = -1; for (auto c: ns) { for (auto i = 0; i < c - '0'; ++i) *p++ = 0; *p++ = 1; } *p = 2; return code; } int main() { for (auto n: {-201, -5, 0, 5, 1234}) { auto code = encodeArray(n); std::cout << n << ": "; for (auto p = code; *p != 2; ++p) std::cout << *p; std::cout << '\n'; delete[] code; } }

Awesome!!!
Topic archived. No new replies allowed.