Function does not return a value, while using a vector in c++

Question

The below function works fine when using an integer array(minNumCoins) but does not return anything while using a vector instead of an array. Can anyone tell me why?

int dp_change(const vector<int> &coins, int money, int n){ //vector<int> minNumCoins(n); int minNumCoins[n]; int numCoins = 0; minNumCoins[0] = 0; for( int m = 1; m <= money; m++){ minNumCoins[m] = 100000; for(int i = 0; i < coins.size(); i++){ if(m >= coins[i]){ numCoins = minNumCoins[m - coins[i]] + 1; if(numCoins < minNumCoins[m]){ minNumCoins[m] = numCoins; } } } } //return minNumCoins.at(money); return minNumCoins[money]; }

Main function

int main() { int n, money; cin >> money; cin >> n; vector<int> coins(n); for(int i = 0; i < n; i++){ cin >> coins[i]; } //int num_of_coins = dp_change(coins, money); cout << "Number of coins = " << dp_change(coins, money, n); return 0; }

Sample

Input: > 20 <br> 2 <br> 10 <br> 1

Output:

Number of coins = 2

Can you give an example or two showing some calls to the function, and what outputs you expect? — NicholasM
– NicholasM, Commented Jan 13, 2021 at 17:16

Andrey Semashev · Accepted Answer · 2021-01-13 17:25:22Z

2

In this piece of code:

 for( int m =1 ; m<=money; m++){ minNumCoins[m] = 100000;

m can become out of bounds if money >= n, which it is in your example input (money=20, n=2). As a result, your program crashes before it gets to output anything.

edited Jan 13, 2021 at 17:25

answered Jan 13, 2021 at 17:21

Andrey Semashev

10.9k1 gold badge21 silver badges33 bronze badges

Sign up to request clarification or add additional context in comments.

8 Comments

Marek R Over a year ago

Same found by address sanitizer.

Nish Over a year ago

It works fine when I'm using an array for minNumCoins. But does not work when I'm using a vector. That's what confuses me.

Andrey Semashev Over a year ago

@Nish The array is placed on the stack, which is likely mapped where the program accesses it, so the program processes garbage and moves on. The vector is allocated on the heap, and the chances of you hitting an unallocated page are greater. In any case, this is undefined behavior.

Marek R Over a year ago

@Nish see link I've provied. It never works. You have buffer overflow error. In case of array this undefined behavior doesn't cause crash immediately.

user4581301 Over a year ago

@Nish Out of bounds access results in Undefined Behaviour. UB is one of the most feared things in all of programming because among the possible outcomes is exactly what you expect to happen. Sometimes the first time you notice you have a bug is when the program crashes at the worst possible time.

|

Jahirul Islam Monir · Accepted Answer · 2021-01-14 05:04:09Z

int dp_change(const vector<int> &coins, int money, int n){ vector<int> minNumCoins(n); //int minNumCoins[n]; int numCoins = 0; minNumCoins[0] = 0; for( int m =1 ; m<n; m++){ minNumCoins[m] = 100000; for(int i=0; i< coins.size(); i++){ if( m >= coins[i]){ numCoins = minNumCoins[m-coins[i]] +1; if( numCoins < minNumCoins[m]){ minNumCoins[m] = numCoins; } } } } //return minNumCoins.at(money); return minNumCoins[any value which is less then n (0-(n-1))]; }

Let me know whether my suggestion works or not. Some things might cause the error while using vector.

you were checking in the outer loop.. for( int m =1 ; m<=money; m++){ here I think m<n will be the correct condition for the loop to work. If money is bigger than n, then out-of-bounds error will occur thus resulting in the code crash. if money = 10, n = 4, then the array out of bound error will occur.

plus return will be like this. return minNumCoins[n];

Or you can declare the minNumCoins array with size minNumCoins[money]

Now implement your logic properly and hopefully, you'll get the desired result.

vector works fine when the size is money, instead of n. Earlier it worked for array(with size n) while it didn't work for vector. That really confused me.

Collectives™ on Stack Overflow

Function does not return a value, while using a vector in c++

Sample

2 Answers 2

8 Comments

1 Comment

Hot Network Questions

Collectives™ on Stack Overflow

Sample

2 Answers 2

8 Comments

1 Comment

Related