Solution is not working if i update the variable to INT_MAX.

Revision en4, by Thanos_I_am_inevitable, 2024-01-27 15:51:10

Hi everyone, I am solving a problem where i need to find the min number of coins such that total sum is equal to sum. My given solution is not working if i use long long ans = INT_MAX; but it is working long long ans = 10000000; for the given testcase. Can somebody help me to find the issue why it is not working with INT_MAX? For example, if the coins are {1,5,7} and the desired sum is 11, an optimal solution is 5+5+1 which requires 3 coins.

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define f(i, p, q) for (int i = p; i < q; i++)

ll dp[1000003];

long long solve(int n, int sum, int *ar) {
    if (sum == 0) return 0;
    if (dp[sum] != INT_MAX) return dp[sum];

    // long long ans = 10000000;
     long long ans = INT_MAX;

    for (int i = 0; i < n; i++) {
        if (sum - ar[i] >= 0) {
            ans = min(ans, 1 + solve(n, sum - ar[i], ar));
        }
    }

    dp[sum] = ans;
    return ans;
}
int main()
{
    int n,m;
    cin >> n>>m;
    int ar[n];
    f(i,0,n)cin>>ar[i];
    f(i,0,1000003)dp[i]= INT_MAX;
    int a =solve(n,m, ar);
    cout<< ((a== 10000000)? -1 : a);
}

100 1000000 649304 85832 159093 841262 930486 225095 306941 914339 469211 156923 460959 236712 440066 842678 379057 615269 321673 694036 378785 792217 78290 15844 644234 752342 102458 30237 191522 388758 697655 113684 20857 639493 641307 527161 977787 505822 196847 735190 169901 417528 342499 102964 907594 780802 577476 162325 790726 579970 148134 144070 624899 392951 594195 813112 534969 856431 25058 630213 641105 636550 762730 873997 275210 717753 243026 915205 52253 613173 751823 647785 928932 305278 858885 496267 717378 426281 245531 139541 942976 912031 550043 194533 504278 552822 805186 950257 673230 484067 790808 762595 590958 799224 711398 599947 858840 212470 820350 710862 546121 159727

Tags dp, recursion

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en7 English Thanos_I_am_inevitable 2024-01-27 16:20:20 122
en6 English Thanos_I_am_inevitable 2024-01-27 15:52:11 26 Tiny change: ' INT_MAX; but it is' -> ' INT_MAX; and it is taking too long but it is'
en5 English Thanos_I_am_inevitable 2024-01-27 15:51:31 0 (published)
en4 English Thanos_I_am_inevitable 2024-01-27 15:51:10 121
en3 English Thanos_I_am_inevitable 2024-01-27 15:50:31 75
en2 English Thanos_I_am_inevitable 2024-01-27 15:48:28 964
en1 English Thanos_I_am_inevitable 2024-01-27 15:46:20 786 Initial revision (saved to drafts)