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

int [n] a;

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

number[0] = a[0]*pow(10,0);
number[1] = a[0]*pow(10,1)   a[1]*pow(10,0);
number[2] = a[0]*pow(10,2)   a[1]*pow(10,1)   a[2]*pow(10,0);
number[3] = a[0]*pow(10,3)   a[1]*pow(10,2)   a[2]*pow(10,1)   a[3]*pow(10,0);
number[n] = a[0]*pow(10,n-1)  ...  a[n-1]*pow(10,0)

For example if I have an array[4] = {9,8,7,6}; I would have the following numbers: {9 ,98 ,987, 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:

int numberA = 0;
vector<int>numberAList; 
numberA = num[0]*(pow(10,0));
    numberAList.push_back(numberA);
    numberA = 0;
    for (int i = 0; i < n-1; i   ){
        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 found the solution:

int numberA=0;
vector<int>numberAList;
for (int i = 0; i < n-1 ; i   ){
        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]<<" ";
}

The time and space complexity for this is just log(n)

CodePudding user response：

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.

CodePudding user response：

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