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)
>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.
- Have a variable
currentthat tracks the current value you are at - Have an array
resto accumulate the results as you iterate over the input array,nums. - For each
nums_iin the arraynums, do the following, respecting the order:
current *= 10current += 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.