How to write an algorithm to construct numbers from items in array

user_5611080 0
Viewed 131

Edit: I have sorted array in descending order (a[0] is the largest)

int [n] a;  (n_max = 18)

each item in the array has an integer with value range: 0 -> 9. I want to construct 2 groups of numbers from the item in the array such that:

//group A: 
numberA[0] = a[0]*pow(10,0);
numberA[1] = a[0]*pow(10,1) + a[1]*pow(10,0);
numberA[2] = a[0]*pow(10,2) + a[1]*pow(10,1) + a[2]*pow(10,0);
numberA[3] = a[0]*pow(10,3) + a[1]*pow(10,2) + a[2]*pow(10,1) + a[3]*pow(10,0);
numberA[n] = a[0]*pow(10,n-1) +...+ a[n-1]*pow(10,0)

//group B: 
numberB[0] = a[0]*pow(10,0);
numberB[1] = a[0]*pow(10,0) + a[1]*pow(10,1);
numberB[2] = a[0]*pow(10,0) + a[1]*pow(10,1) + a[2]*pow(10,2);
numberB[3] = a[0]*pow(10,0) + a[1]*pow(10,1) + a[2]*pow(10,2) + a[3]*pow(10,3);
numberA[n] = a[0]*pow(10,0) +...+ a[n-1]*pow(10,n-1)

For example if I have an array[4] = {9,8,7,6}; I would have the following numbers: numberA[] = {9 ,98 ,987, 9876} and numberB = {6, 76, 876, 9876}

Could anyone educate me with some algorithms using for loop, recursive or anything witty and also the time + space complexity of it ?

My attempt so far:

long long int numberA = 0;
vector<long long int>numberAList; 
numberA = num[0]*(pow(10,0));
numberAList.push_back(numberA);
numberA = 0;
for (int i = 0; i < n-1; i++ ){               // complexity: O(logn) & this algorithm is wrong
    for (int j = i+1; j<n-1; j++){
        numberA += num[i]*pow(10,n-1-j);
        cout<<"numberA"<<numberA<<endl;
    }
    numberAList.push_back(numberA);
}

for (int i = 0; i < (n-2); i++ ){
    cout<<numberAList[i]<<" ";
}

After suggestion from user1984. I made the codes:

long long int numberA=0;
vector<long long int> numberAList;
for (int i = 0; i < n-1 ; i++ ){                  // complexity O(n)
    numberA *= 10;
    numberA += num[i];
    cout<<i<<", numberA: "<<numberA<<endl;
    numberAList.push_back(numberA);
}

for (int i = 0; i < n-1; i++ ){
    cout<<numberAList[i]<<" ";
}

long long int numberB = 0;
vector<long long int> numberBList;                        
for (int i = 0; i < n; i++ ){                           // complexity O(n)
    int j = i+1;
    if (j<n){
        for (j ; j<n; j++ ){
            numberB += num[j]*(pow(10,n-j-1));
        }
        numberBList.push_back(numberB);
        numberB=0;
    }
}

cout<<"numberBlist: "<<endl;
for (int i = 0; i < (n-1); i++ ){
    cout<<numberBList[i]<<" ";
}

The code works ok with short numbers; however, with large number, I start to see some weird results, even after I changed the data type to long long int.

Could anyone help?

// if input = 94321

numberBlist:
94321 4321 321 21 1
numberAlist:
9 94 943 9432 94321

// but with input = 999999999999999999
numberBlist:
100000000000000016 10000000000000000 999999999999999 99999999999999 9999999999999 999999999999 99999999999 9999999999 999999999 99999999 9999999 999999 99999 9999 999 99 9
numberAlist:
9 99 999 9999 99999 999999 9999999 99999999 999999999 9999999999 99999999999 999999999999 9999999999999 99999999999999 999999999999999 9999999999999999 99999999999999999
algorithm c++
2 Answers

This looks like an assignment, so I'm not going to provide code, but a (hopefully), clear approach that helps you to solve the problem in whatever language you prefer.

  1. Have a variable current that tracks the current value you are at
  2. Have an array res to accumulate the results as you iterate over the input array, nums.
  3. For each nums_i in the array nums, do the following, respecting the order:
  • current *= 10
  • current += nums_i
  • push current onto res

That's it. I think the approach is self explanatory, but if you feel it needs more elaboration, please ask.

Update based on OP's recent edit: To deal with arbitrary size integers you have 2 options:

  1. Use a library that handles arbitrary sized number arithmetic, like gmplib, and go with an algorithm like the one you currently have or a similar one.
  2. Use the fact that you don't change the base of the number and employ string/char concatenation. If you need to convert it to an integer at the end, you can use a library. Note that these libraries use bit manipulation techniques and have been optimized to work very fast. Read for example this informative article for details.

A note on the test you ran on large numbers: "999999999999999999" is smaller than a 64 bit signed integer, so the current algorithm shouldn't have worked since a "long long" in c++ is guaranteed to be at least 64 bits. I'm not much familiar with c++ but, since not all the parts of the code are shared, look if you have a place where you are storing that large value in some smaller data type that may overflow.

user_77556650

With std::partial_sum, you might do

std::vector<int> nums{9, 8, 7, 6};
std::vector<int> res(nums.size());
std::partial_sum(nums.begin(), nums.end(),
                 res.begin(),
                 [](int acc, int n){ return 10 * acc + n; });

Demo

user_26845390
Related