Given an array auction of positive amounts and a number bidding which initially needs to be found in the auction array. Our task is to find the final value of the bidding.
The search follows given conditions:
- When bidding value is found in the array; it is multiplied by three.
- Otherwise stop the process.
- Return the final value of the bidding.
Examples :
Input array: {2, 5, 6, 18, 11, 7}, bidding = 2
Output : 54
Explanation :
2 is found in array, so bidding = 2*3 = 6
6 is found in array, so bidding = 6*3 = 18
18 is found in array, so bidding = 18*3 = 54
54 is not found in array, so return final value of bidding.
Input array: {81, 3, 4, 8, 27, 17, 9}, bidding = 3
Output : 243
Explanation :
3 is found in array, so bidding = 3*3 = 9
9 is found in array, so bidding = 9*3 = 27
27 is found in array, so bidding = 27*3 = 81
81 is found in array, so bidding = 81*3 = 243
243 is not found in array, so return final value of bidding.
Approach :
The idea is to use linear search. Traverse the array to look for the initial bidding value. If bidding is present then triple the value and look again in the array. If bidding value is not found in the array then return its value.
Time Complexity : O(n*n)
Space Complexity : O(1)
Below is the code implementation :
//program for above approach
#include <bits/stdc++.h>
using namespace std;
//Utility function
int findFinalBiddingValue(vector<int>& nums, int bidding) {
bool b = true;
while(b){
int i = 0;
for(i = 0; i<nums.size(); i++){
if(nums[i] == bidding){ bidding *= 3; break;}
}
if(i == nums.size())
b = false;
}
return bidding;
}
//Main function
int main() {
vector<int> arr {81, 3, 4, 8, 27, 17, 9};
int bidding =3;
int final_bid=findFinalBiddingValue(arr,bidding);
cout<<"Final bidding value is= "<<final_bid;
return 0;
}