Re-sorting an array of integers based on distinct digits from even to odd

Question

My task was to receive an array of integers and then reassemble the array as required:

• The array size is to be of element index 0
• The next element (index 1) has the number of even distinct digits (digits that appear in only one integer input but not the rest).
• And the next pairs (if any) of elements will store the value of even digits and their number of occurrences in the given array.

• After all the even pairs are exhausted, the next element will have the number of odd uncommon digits and then followed by the odd digits and their occurrences.

  Input {1201, 6266, 35, 77}

  Output {15, 2, 0, 1, 6, 3, 4, 1, 2, 3, 1, 5, 1, 7, 2}

Here is my brute force attempt. How can I improve my logic and shorten my code without the use of a vector?

#include <iostream>
using namespace std;
int* getUncommonDigitStatistics(int*, int);
int main() {
 int testAry[] = { 1201, 6266, 35, 77 };
 int size = 4;
 int* result;
 //int* result2 = getUncommonDigitStatistics(testAry, size);
 result = getUncommonDigitStatistics(testAry, size);
 for (int i = 0; i < result[0]; i++) {
 cout << result[i] << endl;
 }
 return 0;
}
int* getUncommonDigitStatistics(int* input, int size) {
 bool isCommon[10] = { false };
 int digitCounter[10] = { 0 };
 int* uncommonArray;
 int newSize;
 int evens = 0;
 int odds = 0;
 int currentInt;
 int currentDigit;
 int searchInt;
 int searchDigit;
 int i, j;
 for (i = 0; i < size; i++) {
 // For each integer
 currentInt = *(input + i);
 if (currentInt < 0) {
 currentInt = -currentInt;
 }
 do {
 currentDigit = currentInt % 10;
 // Search each digit
 if (digitCounter[currentDigit] == 0) {
 // If we haven't looked already
 if (isCommon[currentDigit] == false) {
 // If it has not already been found common
 for (j = 0; j < size &&
 isCommon[currentDigit] == false; j++) {
 //Search each other integer
 if (j != i) {
 // Don't search the same one!
 searchInt = *(input + j);
 if (searchInt < 0) {
 searchInt = -searchInt;
 }
 do {
 searchDigit = searchInt % 10;
 // Check each digit
 if (currentDigit == searchDigit) {
 isCommon[currentDigit] = true;
 }
 searchInt /= 10;
 } while ((searchInt > 0) &&
 (isCommon[currentDigit] ==
 false));
 }
 }
 }
 if (isCommon[currentDigit] == false) {
 // We didn't find it
 digitCounter[currentDigit]++;
 }
 }
 else {
 // We've already determined it's uncommon
 digitCounter[currentDigit]++;
 }
 currentInt /= 10;
 } while (currentInt > 0);
 }
 for (i = 0; i < 10; i++) {
 // Count evens/odds. This should have been done in the
 // previous step.
 if (digitCounter[i] > 0) {
 if (i % 2 == 0) {
 evens++;
 }
 else {
 odds++;
 }
 }
 }
 newSize = (3 + (evens * 2) + (odds * 2));
 uncommonArray = new int[newSize];
 *(uncommonArray) = newSize;
 j = 2;
 if (evens > 0) {
 // Assign values for even digits
 *(uncommonArray + 1) = evens;
 for (i = 0; i < 10; i += 2) {
 if (digitCounter[i] > 0) {
 *(uncommonArray + j) = i;
 *(uncommonArray + j + 1) = digitCounter[i];
 j += 2;
 }
 }
 }
 else {
 *(uncommonArray + 1) = 0;
 }
 *(uncommonArray + j) = odds;
 j++;
 if (odds > 0) {
 // Assign values for odd digits
 for (i = 1; i < 10; i += 2) {
 if (digitCounter[i] > 0) {
 *(uncommonArray + j) = i;
 *(uncommonArray + j + 1) = digitCounter[i];
 j += 2;
 }
 }
 }
 return uncommonArray;
}

• Zulan: Why would you not want to use a vector. This code is hardly C++.

Answer 1

I see a number of things that may help you improve your code.

Don't abuse using namespace std

Putting using namespace std at the top of every program is a bad habit that you'd do well to avoid. Know when to use it and when not to (as when writing include headers).

Minimize the scope of variables

Rather than using the old C-style of declaring all variables at the top of a routine, modern C++ allows us to declare variables closer to where they are used which is a benefit for the reader. Additionally, one can reduce the scope of a variable still further by declaring it within a loop context. For example, the code currently contains this line:

for (i = 0; i < size; i++) {

The scope of the variable i could be reduced by writing it instead like this:

for (int i = 0; i < size; i++) {

Use const where practical

Both the testAry and the corresponding argument to getUncommonDigitStatistics should both be declared as const. It's good practice to use it where practical.

Break up long functions into reusable subfunctions

The code could benefit greatly from having the one large getUncommonDigitStatistics broken up into smaller subfunctions.

Fix the memory leak

The code allocates memory using new but never calls delete thus leaking memory.

Simplify your algorithm

There isn't a need to go through the array more than once, as the code comment indicates. The algorithm can be very much simplified as I will show later.

Reconsider the interface

Using old-style C array pointer and size is an error-prone way to do things. Far better would be to use std::vector or std::array if the size is fixed.

Use object orientation

Because you're writing in C++, it would make sense to have methods that operate on a class instead one big long function. Here's one way to do it. First, let's make a DigitStats class:

class DigitStats {
public:
 DigitStats() :
 count{}, unique{}, rare{} 
 {}
 DigitStats(const int *arr, int arrsize) :
 count{}, unique{}, rare{} 
 {
 for (int i=0; i < arrsize; ++i) {
 operator+=(arr[i]);
 }
 }
 DigitStats &operator+=(const int number) {
 if (number == 0) {
 update(0);
 ++count[0];
 return *this;
 }
 int n = number<0 ? -number : number;
 bool found[digits]{false};
 for (int d = n % digits; n; d = n % digits) {
 if (!found[d]) {
 found[d] = true;
 update(d);
 }
 ++count[d];
 n /= digits;
 }
 return *this;
 }
 unsigned rareEven() const { return rare[0]; }
 unsigned rareOdd() const { return rare[1]; }
 unsigned arraySize() const { return 3 + 2 * (rareEven() + rareOdd()); }
 int *getArray() const {
 int *array = new int[arraySize()];
 int n = 0;
 array[n++] = arraySize();
 array[n++] = rareEven();
 for (unsigned i=0; i<digits; i+=2) {
 if (unique[i]) {
 array[n++] = i;
 array[n++] = count[i];
 }
 }
 array[n++] = rareOdd();
 for (unsigned i=1; i<digits; i+=2) {
 if (unique[i]) {
 array[n++] = i;
 array[n++] = count[i];
 }
 }
 return array;
 }
private:
 void update(const int d) {
 if (unique[d]) {
 unique[d] = false;
 --rare[d%2];
 }
 else if (count[d] == 0) {
 unique[d] = true;
 ++rare[d%2];
 } 
 }
 static constexpr unsigned digits = 10;
 unsigned count[digits];
 bool unique[digits];
 unsigned rare[2];
}

Here's how to use it:

int main() {
 const int testAry[] = { 1201, 6266, 35, 77 };
 int size = 4;
 DigitStats ds{testAry, size};
 int *result = ds.getArray();
 for (int i = 0; i < result[0]; i++) {
 std::cout << result[i] << ' ';
 }
 std::cout << std::endl;
 delete[] result;
}

Note that I kept the original interface, but if I were really writing it, I'd use an object instead of a plain array.

Omit return 0

When a C++ program reaches the end of main the compiler will automatically generate code to return 0, so there is no reason to put return 0; explicitly at the end of main.

• erip: While the last point is true, it doesn't make the code more-or-less idiomatic to omit it. Good points otherwise.
• MikeMB: Personally, I wouldn't return the array as a raw pointer. Instead I'd return a vector or - if I absolutely must - a unique ptr. Since I have a c++11 compiler, I view almost any delete as a design error.
• Edward: @MikeMB: Agreed. That was exactly the point I was making in the section titled "reconsider the interface."
• MikeMB: Yes, but why did you keep it in your code then?
• Edward: @MikeMB - The original poster specifically said without using a vector, so I did it that way, but agree that using one or 'std::array' would be better design.

Answer 2

Some illustrative tweaks that you may want to consider for future programs. Rewriting this one may remove the need for them here, but you may encounter the same pattern again.

In

 for (j = 0; j < size &&
 isCommon[currentDigit] == false; j++) {
 //Search each other integer
 if (j != i) {

You avoid comparing when j and i are equal, but you compare twice if j is less than i and currentDigit is not common. You can just say

 for (int j = i + 1; j < size &&
 isCommon[currentDigit] == false; j++) {
 //Search each other integer

Then you don't have to compare j and i at all. And you don't repeat fruitless searches that you've already done. Don't forget to remove the trailing

 }

as well.

Note that I also moved the declaration for j into the for loop. Since you never use that value of j outside that loop, you don't have to declare it earlier.

You say

 j = 2;
 if (evens > 0) {
 // Assign values for even digits
 *(uncommonArray + 1) = evens;
 for (i = 0; i < 10; i += 2) {
 if (digitCounter[i] > 0) {
 *(uncommonArray + j) = i;
 *(uncommonArray + j + 1) = digitCounter[i];
 j += 2;
 }
 }
 }
 else {
 *(uncommonArray + 1) = 0;
 }

but you could write this more simply as

 uncommonArray[1] = evens;
 int j = 2;
 if (evens > 0) {
 // Assign values for even digits
 for (i = 0; i < 10; i += 2) {
 if (digitCounter[i] > 0) {
 uncommonArray[j] = i;
 uncommonArray[j + 1] = digitCounter[i];
 j += 2;
 }
 }
 }

This works because you do the same assignment in both branches of the if. So you can pull it out and get rid of the else branch.

Note that I also changed from your *(uncommonArray + j) notation to the more idiomatic uncommonArray[j] notation. This makes no functional difference, but many of us find it easier to read.

And because I got rid of the original declaration of j, we have to declare it when we initialize it here. You could also use a different variable name, but the two scopes don't overlap.