Follow

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use
Contact

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

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}

MEDevel.com: Open-source for Healthcare and Education

Collecting and validating open-source software for healthcare, education, enterprise, development, medical imaging, medical records, and digital pathology.

Visit Medevel

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)

>Solution :

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.

Add a comment

Leave a Reply

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use

Discover more from Dev solutions

Subscribe now to keep reading and get access to the full archive.

Continue reading