Find pair of given sum in an unsorted arrray

import java.util.*;

import java.lang.*;

import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */

class Codechef

{

    public static List<Integer> findSum(List<Integer> l, int sum)

    {

        Map<Integer, Integer> hm = new HashMap<>();

        List<Integer> result = new ArrayList<>();

        for(int i=0;i<l.size();i++)

        {

            int k = sum-l.get(i);

            if(hm.containsKey(k))

            {

                result.add(hm.get(k));

                result.add(i);

                break;

            }

            else

                hm.put(l.get(i), i);

        }

        

        return result;

    }

    

public static void main (String[] args) throws java.lang.Exception

{

// your code goes here

List<Integer> l = new ArrayList<>();

l.add(5);

l.add(2);

l.add(12);

l.add(7);

l.add(23);

l.add(4);

Integer sum = 9;

List<Integer> result = findSum(l, sum);

System.out.println("The indexes in the array " + l + " that adds upto sum=" + sum + " are " + result);

}

}

Minimum coins needed to make change

#include <iostream>

#include <climits>

using namespace std;

int mem[50][50];

int min(int a, int b)

{

    return a<b ? a:b;

}

int minCoinChange(int c[], int n, int val)

{

    int minCoins = INT_MAX;

    for(int i=0;i<n;i++)

    {

        mem[i][0] = 0;

        int j=0;

        for(;j<=val;j++)

        {

            if(i > 0)

            {

                if(j>=c[i])

                    mem[i][j] = min(mem[i-1][j], 1 + mem[i][j-c[i]]);

                else

                    mem[i][j] = mem[i-1][j];

                

            }

            else

            {

                if(j < c[i])

                    mem[i][j] = 0;

                else

                    mem[i][j] = 1 + j - c[i] ;

                    

            }

        }

        if(minCoins > mem[i][j-1])

            minCoins = mem[i][j-1];

    }

    

    return minCoins;

}

void printCoins(int c[], int n)

{

    for(int i=0;i<n;i++)

        cout << c[i] << ", ";

}

int main() {

// your code goes here

int c[] = {1,6,10};

for(int i=0; i<30; i++)

{

    int val = i;

    cout << "minimum coins required to make change of " << val << " using coins ";

    printCoins(c, sizeof(c)/sizeof(c[0]));

    cout << " = " << minCoinChange(c, sizeof(c)/sizeof(c[0]), val) << endl;

}

return 0;

}

Output -

minimum coins required to make change of 0 using coins 1, 6, 10,  = 0

minimum coins required to make change of 1 using coins 1, 6, 10,  = 1

minimum coins required to make change of 2 using coins 1, 6, 10,  = 2

minimum coins required to make change of 3 using coins 1, 6, 10,  = 3

minimum coins required to make change of 4 using coins 1, 6, 10,  = 4

minimum coins required to make change of 5 using coins 1, 6, 10,  = 5

minimum coins required to make change of 6 using coins 1, 6, 10,  = 1

minimum coins required to make change of 7 using coins 1, 6, 10,  = 2

minimum coins required to make change of 8 using coins 1, 6, 10,  = 3

minimum coins required to make change of 9 using coins 1, 6, 10,  = 4

minimum coins required to make change of 10 using coins 1, 6, 10,  = 1

minimum coins required to make change of 11 using coins 1, 6, 10,  = 2

minimum coins required to make change of 12 using coins 1, 6, 10,  = 2

minimum coins required to make change of 13 using coins 1, 6, 10,  = 3

minimum coins required to make change of 14 using coins 1, 6, 10,  = 4

minimum coins required to make change of 15 using coins 1, 6, 10,  = 5

minimum coins required to make change of 16 using coins 1, 6, 10,  = 2

minimum coins required to make change of 17 using coins 1, 6, 10,  = 3

minimum coins required to make change of 18 using coins 1, 6, 10,  = 3

minimum coins required to make change of 19 using coins 1, 6, 10,  = 4

minimum coins required to make change of 20 using coins 1, 6, 10,  = 2

minimum coins required to make change of 21 using coins 1, 6, 10,  = 3

minimum coins required to make change of 22 using coins 1, 6, 10,  = 3

minimum coins required to make change of 23 using coins 1, 6, 10,  = 4

minimum coins required to make change of 24 using coins 1, 6, 10,  = 4

minimum coins required to make change of 25 using coins 1, 6, 10,  = 5

minimum coins required to make change of 26 using coins 1, 6, 10,  = 3

minimum coins required to make change of 27 using coins 1, 6, 10,  = 4

minimum coins required to make change of 28 using coins 1, 6, 10,  = 4

minimum coins required to make change of 29 using coins 1, 6, 10,  = 5