We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #31: Coin sums
  4. Discussions

Project Euler #31: Coin sums

Sort by

recency

|

37 Discussions

|

  • vidush_rk11
     + 0 comments

    Cpp code C++20

    include

    include

    include

    include

    include

    using namespace std;

    long long modulo=pow(10,9)+7;

    int ceil(int a, int b){ a+= (a%b) ?b-a%b :0;
    return a/b; } int main() { int t; cin>>t;

    vector<int> numbers{5,10,20,50,100,200};

int n=pow(10,5);

long long answers[n+1];

for (int i=0; i<n+1; i++){
    answers[i]=ceil(i+1,2);
}

for (int i: numbers){
    for (int j=i; j<n+1; j++){
        answers[j]+=answers[j-i];
        answers[j]%=modulo;
    }
}


while (t--){
    cin>>n;

    cout<<answers[n]<<endl;
}
return 0;

    }

  • blackspring
     + 0 comments
    #python
n=[int(input()) for x in range(int(input()))]
temp=[0]*(max(n)+1)
temp[0] = 1
coins=[1, 2, 5, 10, 20, 50, 100, 200]
for i in range(8):
    for j in range(coins[i], max(n)+1):
        temp[j] += temp[j-coins[i]]
for x in n:
    print(temp[x] %(10**9+7))

  • mr_vero
     + 0 comments

    Took me 2 minutes to solve it 100/- Python3:

    MOD = 10**9 + 7

def calculate_combinations(limit, multiples):
    lis = [0] * (limit + 1)
    lis[0] = 1

    for i in multiples:
        for n in range(limit - i + 1):
            lis[n + i] += lis[n]
            lis[n + i] %= MOD

    return lis

no = 10**5
multiples = [1, 2, 5, 10, 20, 50, 100, 200]

lis = calculate_combinations(no, multiples)

for _ in range(int(input())):
    n = int(input())
    print(lis[n] % MOD)

  • ketan_patel25
     + 0 comments

    Java Code 

    import java.io.*;
import java.util.*;
import java.math.*;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
      
    {
        BigInteger table[]= new BigInteger[100001];
    
    int coin[]= new int[]{1,2,5,10,20,50,100,200};
    for(int i=0;i<table.length;i++)
    {
        table[i]=BigInteger.ZERO;
    }
    table[0]=BigInteger.ONE;
    for(int i=0;i<8;i++)
    {
        for(int j=coin[i];j<table.length;j++)
        {
            table[j]=table[j].add(table[j-coin[i]]);
        }
    }
        Scanner sc= new Scanner(System.in);
        int num=Integer.parseInt(sc.nextLine());
        for(int i=0;i<num;i++)
        {
            int tem=Integer.parseInt(sc.nextLine());
            System.out.println(table[tem].mod(BigInteger.valueOf(1000000007)));
        }
    }
    }
}

  • vidush_rk11
     + 0 comments

    Lovely challenge, 100/- points python3

    no=10**5
multiples=[1,2,5,10,20,50,100,200,]
lis=[]
for i in range(no+1):
    lis.append(i//2+1) #it reduced my time efficiency by 3 times in my earlier code which was slower

for i in multiples[2:]:
    for n in range(no-i+1):
        lis[n+i]+=lis[n]
        
for _ in range(int(input())):
    n=int(input())
    print(lis[n]%(10**9+7))