Apply For Jobs
Get Hiring UpdatesCognizant GenC Elevate Sample Coding Question 10
Question 10
In this article, we will discuss about Coding Question with their solution in C++ and java. In this Question , Adil is pondering over the number of ways in which he can pay for the movie. He has x1, x2, x3, x4 coins of values 1,2,5 and 10 respectively. He wants to determine the number of ways in which he can pay an amount A.
Question 10
After Watching a movie at PVR, Adil is pondering over the number of ways in which he can pay for the movie. He has x1, x2, x3, x4 coins of values 1,2,5 and 10 respectively. He wants to determine the number of ways in which he can pay an amount A.
You need to fill in a function that returns the number of ways to pay total amount
Input Specifications:
Input 1: An integer value denoting the total amount to be paid
Output Specification:
Return an Integer value denoting the number of ways to pay the total amount
Example1:
Input1: 40
Output : 195
Example2:
Input1: 4
Output : 3
#include <iostream>
#include <climits>
using namespace std;
int coinsExchange(int amt, int *deno, int n, int *dp) {
// base case
if (amt == 0) {
return dp[amt] = 0;
}
if (dp[amt] != -1) {
return dp[amt];
}
// recursive case
int ans = INT_MAX;
for (int i = 0 ; i < n ; i++) {
if (amt >= deno[i]) {
int sa = coinsExchange(amt - deno[i], deno, n, dp);
if (sa != INT_MAX) {
ans = min(sa + 1, ans);
}
}
}
return dp[amt] = ans;
}
int main() {
int deno[4] = {1, 2, 5, 10};
int amt;
cin>>amt;
int *dp = new int[amt + 1];
for (int i = 0 ; i <= amt ; i++) {
dp[i] = -1;
}
cout << coinsExchange(amt, deno, 4, dp) << endl;
return 0;
}
import java.io.*;
import java.util.*;
public class Coin {
static int count( int S[], int m, int n )
{
if (n == 0)
return 1;
if (n < 0)
return 0;
if (m <=0 && n >= 1)
return 0;
return count( S, m - 1, n ) +
count( S, m, n-S[m-1] );
}
public static void main(String[] args)
{ Scanner sc = new Scanner(System.in);
int total = sc.nextInt();
int arr[] = {1, 2, 5,10};
int m = arr.length;
System.out.println( count(arr, m, total));
}
}
