C++

Forum

 
EncodeArray Problem - I'm lost on this one

CollinsLainzo (24)
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.

keskiverto (10367)
Start with:
Make one pass through the digits of the number to compute the size of the encoded array.


1
2
3
4
5
6
7
8
 
int* encodeArray(int n)
{
  // one pass that prints each digit of n separately

  // print required size of the array

  return nullptr;
}
lastchance (6980)
There is one very significant issue with the prototype for that function.
dutch (2548)
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
lastchance (6980)
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
dutch (2548)
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.
chicofeo (640)
This is a horrible code, due to the constraints of the specifications. This is to provide an idea of one way (out of many).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
 
#include <iostream>
#include <cstdlib> // 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
keskiverto (10367)
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?
lastchance (6980)
@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
chicofeo (640)
@lastchance, I concur with the usability issue. I modified due to unnecessary duplication on my first draft.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
 
#include <iostream>
#include <cstdlib> // 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
lastchance (6980)
Here's a couple of unconventional ways. Neither meet the exact specifications of the assignment.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 
#include <iostream>
#include <cstdlib>
#include <string>
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;
   }
}



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
 
#include <iostream>
#include <cstdlib>
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
dutch (2548)
Nice one! But if you're modifying the prototype, you may as well go all the way and return a vector.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 
#include <iostream>
#include <string>
#include <vector>

auto encodeNumber(int n)
{
    std::vector<int> 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';
   }
}
lastchance (6980)
Nice too! Actually, I might just as well have returned the string!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
#include <iostream>
#include <cstdlib>
#include <string>
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
dutch (2548)
Arrgghhh! Didn't think of that!
Alternatively, use the "2 at the end" trick to stick to the given prototype.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 
#include <iostream>
#include <string>

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;
   }
}

chicofeo (640)
Awesome!!!
Topic archived. No new replies allowed.