Cognizant GenC Elevate Coding Questions 2023

August 31, 2023

GenC Elevate Coding Questions for 2023 graduates

This section is the most important part of the Cognizant GenC Elevate Hiring. Cognizant programming test Questions are of moderate difficulty, in this post you will find all the most important and latest pattern based sample Cognizant GenC Elevate Coding Questions with their solutions.

Detailed Analysis for CTS GenC Elevate Coding Questions

This will be the second section of GenC Elevate online test. In this section you will have to solve a total of 4 coding questions in 60 mins. The difficulty level of the questions will range from moderate to high. In previous year online test, Cognizant restricted the students to use only Java and Python for solving the coding questions, although there is no such official announcement this time now, we recommend you give more emphasis on these coding languages.

Gen C Elevate Coding Round	Details
Number of Questions	4 Questions
Time Duration	60 Minutes
Importance	High

Below we have provided some sample practice questions based on the pattern of Cognizant Coding Questions for GenC Elevate, make sure you practice all of them while preparing for GenC Elevate online test.

Practice Questions for Cognizant GenC Elevate Coding Round

Question 1

You want to buy a particular stock at its lowest price and sell it later at its highest price. Since the stock market is unpredictable, you steal the price plans of a company for this stock for the next N days.
Find the best price you can get to buy this stock to achieve maximum profit.

Note: The initial price of the stock is 0.

Input Specification:

Input1: N, number of days
Input2: Array representing change in stock price for the day.

Output Specification:

Your function must return the best price to buy the stock at.

Example1:

Input1: 5
Input2: (-39957,-17136,35466,21820,-26711}
Output: -57093
Explanation: The best time to buy the stock will be on Day 2 when the price of the stock will be -57093.

Example2:

Input1: 5
Input2: (-39957, -17136, 1, 2, -26711)
Output: -80801
Explanation: The best time to buy the stock will be on Day 5 when the price of the stock will be -83801.

Example3:

Input1: 9
Input2: (-4527,-1579,-38732,-43669,-9287,-48068,-30293,-30867,18677}
Output: -207022
Explanation: The best time to buy the stock will be on Day 8 when the price of the stock will be -207022.

C

C++

Java

Python

C

#include<stdio.h>
int main()
{
    int N, ans, price;
    scanf("%d", &N);
   
    int arr[N];
    
    for (int i = 0; i < N; i++)
        scanf("%d", &arr[i]);
    
    price = 0;
    ans = 0;
    for (int i = 0; i < N; i++)
    {
        price = price + arr[i];
        if (ans > price)
            {
                ans = price;
            }
    }
    printf("%d", ans);
}

C++

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int N, ans, price;
    cin>>N;
   
    int arr[N];
    
    for (int i = 0; i < N; i++)
        cin>>arr[i];
    
    price = 0;
    ans = 0;
    for (int i = 0; i < N; i++)
    {
        price = price + arr[i];
        if (ans > price)
            {
                ans = price;
            }
    }
    cout << ans;
}

Java

import java.util.*;
public class Main
{
	public static void main(String[] args)
	{
	    Scanner sc= new Scanner(System.in);   
		int n= sc.nextInt();
		int[] arr = new int[n];
		
		for(int i = 0; i < n; i++)
		{
		    arr[i]=sc.nextInt();
		}
		
		int min=0;
		for(int i = 1; i < n; i++)
		{
		    int sum=0;
		    for (int j = 0; j < i+1; j++)
		    {
		        sum+=arr[j];
		    }
		    if (sum < min)
		    {
		        min=sum;
		    }
	    }
        System.out.println(min);
	}    
}

Python

n = int(input())
arr = []
for i in range(n):
   arr.append(int(input()))
min = 0
for i in range(1, n):
   if sum(arr[:i]) < min:
       min = sum(arr[:i])
print(min)

Question 2

Given a positive whole number n, find the smallest number which has the very same digits existing in the whole number n and is greater than n. In the event that no such certain number exists, return – 1.

Note: that the returned number should fit in a 32-digit number, if there is a substantial answer however it doesn’t fit in a 32-bit number, return – 1.

Example 1:

Input: n = 12
Output: 21
Explanation: Using the same digit as the number of permutations, the next greatest number for 12 is 21.

Example 2:

Input: n = 21
Output: -1
Explanation: The returned integer does not fit in a 32-bit integer

C++

Java

Python

C++

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

void swap(char *a, char *b)
{
	char temp = *a;
	*a = *b;
	*b = temp;
}

void findNext(char number[], int n)
{
	int i, j;

	for (i = n-1; i > 0; i--)
		if (number[i] > number[i-1])
		break;

	if (i == 0)
	{
		cout << "Next number is not possible";
		return;
	}

	int x = number[i-1], smallest = i;
	for (j = i+1; j < n; j++) if (number[j] > x && number[j] < number[smallest])
			smallest = j;

	swap(&number[smallest], &number[i-1]);


	sort(number + i, number + n);

	cout << number; return; } int main() { char digits[]; cin >> digits
	int n = strlen(digits);
	findNext(digits, n);
	return 0;
}

Java

import java.util.*;
public class Main
{
	static void swap(char ar[], int i, int j)
	{
		char temp = ar[i];
		ar[i] = ar[j];
		ar[j] = temp;
	}
	
	static void findNext(char ar[], int n)
	{
		int i;
		
		for (i = n - 1; i > 0; i--)
		{
			if (ar[i] > ar[i - 1]) {
				break;
			}
		}
		
		if (i == 0)
		{
			System.out.println("Not possible");
		}
		else
		{
			int x = ar[i - 1], min = i;
			
			
			for (int j = i + 1; j < n; j++)
			{
				if (ar[j] > x && ar[j] < ar[min])
				{
					min = j;
				}
			}
		
			swap(ar, i - 1, min);
			Arrays.sort(ar, i, n);
			
			for (i = 0; i < n; i++)
				System.out.print(ar[i]);
		}
	}

	public static void main(String[] args)
	{
	    Scanner sc = new Scanner(System.in);
	    int n =sc.nextInt();
	    String s = sc.next();
		char digits[] = s.toCharArray();
		
		findNext(digits, n);
	}
}

Python

arr = []
def permute(s,ans):
    n = len(s)
    if (n == 0):
        arr.append(ans)
        return
    for i in range(n):
        ch = s[i]
        L = s[0:i]
        R = s[i + 1:]
        REM = L+ R
        permute(REM,ans + ch)
ans= ""
s = input()
n = len(s)
permute(s,ans)
arr = list(set(arr))
arr.sort()
ind = arr.index(s)
if(ind == len(arr)-1):
    print(-1)
else:
    print(arr[ind+1])

Question 3

Henry is extremely keen on history and every one of the ages of his family. He does a ton of exploration and understands that he has plummeted from the incomparable Amaya line. After a ton of looking through old records and the most recent records of the general public, he can discover all the parent-kid connections in his family right from the extraordinary ruler Ming of the tradition to himself.

These connections are given in the structure of a direct exhibit where the emperor is at the main position and his kids are at pos (2i + 1) and (2i + 2)

This is the pattern followed throughout.

Henry needs to sort out every one of the kin of individual X from the information.

Write a program for Henry to figure out all the siblings of person X from the data.
Return the sorted list of all of Henry’s siblings.

If no sibling return {-1}

input 1: N, the length of the array
input2: An array representing the ancestral tree
input 3: X, the person whose siblings are sought.
output – return the array of all siblings in increasingly sorted order.

Example 1 :

input 1: 5
input 2: {1,2,3,4,5}
input 3: 1
output: {-1}
Explanation: x is the root of the tree and has no siblings

Example 2 :

input 1: 6
input 2: {1,2,3,4,5,6}
input 3: 5
output: {4,6}
Explanation: {2,3 } are the children of {1}. {4,5,6 } are the children of {2,3}, thus the siblings of x= 5 are {4,6}

Java

Python

Java

import java.util.*;
 
public class Main
{
    Node root;
    static class Node
    {
        int data;
        Node left, right;
    
        Node (int data) 
        {
            this.data = data;
            this.left = null;
            this.right = null;
        } 
    } 

    public static void main (String[]args)
    {
        Main t2 = new Main ();
        Scanner sc = new Scanner (System.in);
        int length = sc.nextInt ();
        int arr[] = new int[length];
    
        for (int i = 0; i < length; i++)
        {
            arr[i] = sc.nextInt ();
        }
        int target = sc.nextInt ();
        t2.root = t2.insertLevelOrder (arr, t2.root, 0);
    
        Set < Integer > sets = t2.levelOrderBottom (t2.root, target);
        sets.remove (target);
        System.out.println (sets);
    }   
    public static Node insertLevelOrder (int[]arr, Node root, int i) 
    {
        if (i < arr.length)
        {
            Node temp = new Node (arr[i]);
            root = temp;
            root.left = insertLevelOrder (arr, root.left, 2 * i + 1);
            root.right = insertLevelOrder (arr, root.right, 2 * i + 2);
        }
        return root;
    }

    public Set < Integer > levelOrderBottom (Node root, int target)
    {
        if (root == null)
        {
        	return null;
        }
        Queue < Node > q = new LinkedList <> ();
        q.offer (root);
    
        while (!q.isEmpty ())
        {
            int qsize = q.size ();
            Set < Integer > temp = new HashSet <> ();
            
            for (int i = 0; i < qsize; i++)
	        {
                Node child = q.poll ();
                temp.add (child.data);
                
                if (child.left != null)
	            {
                    q.offer (child.left);
                }
                if (child.right != null)
	            {
                    q.offer (child.right);
                }
            }
            if (temp.contains (target))
                return temp;
        }
        return null;
    }
}

Python

def identify_siblings(tree_array, x):
    tree_len = len(tree_array)
    index = tree_array.index(x)
    level = 0
    start_index = level
    number_of_nodes = 0
    while start_index < tree_len:
    	end_index = pow(2, level) + start_index
    	if x in tree_array[start_index:end_index]:
    		break
    	level += 1
    	start_index = (2 * start_index) + 1
    final_array = tree_array[start_index:end_index]
    final_array.remove(x)
    return final_array if final_array else [-1]

n = int(input())
arr = []
for i in range(n):
    arr.append(int(input()))
x = int(input())
print(identify_siblings(arr, x))

Question 4

Rohan and his team are participating in the Treasure Hunt event of college in which in each step they have to solve one problem to get a clue about the Treasure location. Rohan’s team has performed very well and reached the final step where they have to provide a code of a problem to get a final clue about treasure .

Given a string s, they need to find the longest palindromic subsequence’s length in s.
A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

The string contains only lowercase letters.

Write a program to help Rohan’s team that takes in input as String x and returns the length of the longest palindromic subsequence of x.

Input Specification:

input1: string input

Output Specification:

Return the length of the longest palindromic subsequence

Example 1:

Input: s = “bbbab”
Output: 4
Explanation: One possible longest palindromic subsequence is “bbbb”.

Example 2:

Input: s = “cbbd”
Output: 2
Explanation: One possible longest palindromic subsequence is “bb”.

C++

Java

Python

C++

#include<iostream>
#include<cstring>
using namespace std;

int max (int x, int y) 
{
    return (x > y)? x : y; 
}

int lps(char *str)
{
    int n = strlen(str);
    int i, j, cl;
    int L[n][n]; 

    for (i = 0; i < n; i++)
	    L[i][i] = 1;

    for (cl = 2; cl <= n; cl++)
	{
		for (i = 0; i < n-cl+1; i++)
		{
		    j = i + cl-1;
		    if (str[i] == str[j] && cl == 2)
		        L[i][j] = 2;
		    else if (str[i] == str[j])
		        L[i][j] = L[i+1][j-1] + 2;
		    else L[i][j] = max(L[i][j-1], L[i+1][j]);
		}
	}
	return L[0][n-1];
}

int main()
{
    char seq[20];
    cin >> seq;
	int n = strlen(seq);
	printf("%d", lps(seq));
	getchar();
	return 0;
}

Java

import java.util.*;
public class Main
{
	static int max (int x, int y) 
	{
	    return (x > y)? x : y; 
	    
	}

	static int lps(String seq)
	{
	    int n = seq.length();
	    int i, j, cl;
    	    int L[][] = new int[n][n];
	
    	    for (i = 0; i < n; i++)
	    	L[i][i] = 1;
		
		for (cl = 2; cl <= n; cl++)
		{
			for (i = 0; i < n-cl+1; i++)
			{
				j = i+cl-1;
				if (seq.charAt(i) == seq.charAt(j) && cl == 2)
    				L[i][j] = 2;
				else if (seq.charAt(i) == seq.charAt(j))
	    			L[i][j] = L[i+1][j-1] + 2;
				else
		    		L[i][j] = max(L[i][j-1], L[i+1][j]);
			}
		}
		return L[0][n-1];
	}
	
	public static void main(String args[])
	{
	        Scanner sc = new Scanner(System.in);
		String seq = sc.next();
		int n = seq.length();
		System.out.println(""+ lps(seq));
	}
}

Python

s = input()
n = len(s)
rev = s[::-1]
dp = [[0 for _ in range(n+1)] for _ in range(n+1)]

for i in range(1, n+1):
    for j in range(1, n+1):
        if s[i-1] == rev[j-1]:
            dp[i][j] = 1 + dp[i-1][j-1]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])

print(dp[n][n])

Question 5

Given a number n, the task is to find the remainder when n is divided by 11. The input number may be very large.

Since the given number can be very large, you can not use n % 11.

Input Specification:

inputs a large number in the form of a string

Output Specification:

Return the remainder modulo 11 of input1

Example1:

Input: str = 13589234356546756
Output: 6

Example2:

Input: str = 3435346456547566345436457867978
Output: 4

Example3:

input: str = 121
Output: 0

C++

Java

Python

C++

#include<bits/stdc++.h>
using namespace std;
 
int remainder(string str)
{
    int len = str.length();
 
    int num, rem = 0;
 
    for (int i = 0; i < len; i++)
    {
        num = rem * 10 + (str[i] - '0');
        rem = num % 11;
    }
    return rem;
}

int main()
{
    string str;
    cin >> str;
    cout << remainder(str);
    return 0;
}

Java

import java.util.*;
import java.io.*;
public class Main
{
	static int remainder(String str)
	{
		int len = str.length();
		int num, rem = 0;
		
		for (int i = 0; i < len; i++)
		{
			num = rem * 10 + (str.charAt(i) - '0');
			rem = num % 11;
		}
		return rem;
	}
	
	public static void main(String args[])
	{
	    Scanner sc = new Scanner(System.in);
		String str = sc.next();
		System.out.println(remainder(str));
	}
}

Python

s, rem = input(), 0

for i in s:
    rem = (rem * 10 + int(i)) % 11

print(rem)

Question 6

Jasleen has bought a new bulb factory. The factory has a single file of machines, numbered from 1 to N. Each machine has a certain number of fully prepared bulbs.
Jasleen has a rule she wants to follow. She wants to collect an equal amount of bulb from
each machine from which she collects bulbs.

Jasleen can start collecting bulb from any machine, but once she starts collecting, she collects
from every consecutive machine until she reaches the last machine she wants to collect from. Find the maximum number of bulbs she can collect.

Input Specification:
Input1: N, the number of machines
Input2: An array of N elements (a1,a2 a3……aN], denoting the number of fully prepared bulbs in each machine of the factory.

Output Specification:
An integer output denoting the maximum number of bulbs that Allie can collect.

Example 1:
input1: 3
Input2: [1,2,3]

Output: 3

Example 2:
input1: 4
Input2: [5,8,9,10]

Output: 20

Java

Java

import java.util.*;
public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int a[] = new int[n];
    for (int i = 0; i < n; i++)
      a[i] = sc.nextInt();
    Arrays.sort(a);
    ArrayList < Integer > a1 = new ArrayList < > ();

    for (int i = a.length - 1; i >= 0; i--) {
      int x = 0;
      x = a[i] * (a.length - i);
      a1.add(x);
    }

    for (int i = 0; i < a1.size(); i++) {
      if (a1.get(a1.size() - 1 - i) >= a1.get(i)) {
        System.out.println(a1.get(a1.size() - 1 - i));
        break;
      }
    }
  }
}

Question 7

An astrologer gives a matrix to devilliers and tells him to add a largest row sum and largest column sum of the given matrix.The number which appears as a result is his lucky number for the final match jersey.

Write a program that adds up the largest row sum and the largest column sum from an N- rows*M-columns array of numbers to help devilliers for finding his lucky number for the final match jersey.

As a preliminary phrase , you should reformat the sequence of numbers as a matrix, whose number of rows and columns are to be specified as arguments.

Input Specification:

Input 1: Integer for row dimension of the array
Input 2: Integer for column dimension of the array
Input 3: Array elements to be entered in row major.

Output Specifications:

Largest row sum+ Largest column sum

Example 1:
Input1:4
Input2: 4
Input3: {1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4}

Output: 26

Explanation:
The array has 4 rows (input1) and 4 columns (input2). The largest sum among the four columns is 10 and the largest sum among the four rows is 16. We get the final sum of 26 (10+16).

Example 2:
Input1:2
Input2: 2
Input3: {1,2,5,6}

Output: 19

Explanation:

The array has 2 rows (input1) and 2 columns (input2). The elements in the first row are 1 and 2 and the elements in the second row are 5 and 6 (input3). The largest sum among the two columns is 8(2+6) By adding those two up. We get the final sum of 19 (11+8).

Example 3:
Input1: 3
Input2: 3
Input3: {3,6,9,1,4,7,2,8,9}

C++

Python

C++

#include<bits/stdc++.h>
using namespace std;
int main ()
{
    int N, M;
    cout << "Enter number of rows : ";
    cin >> N;
    cout << "\nEnter number of columns : ";
    cin >> M;
    int Matrix[N][M];
    cout << "\nEnter elements row-wise : \n";
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> Matrix[i][j];
        }
    }
    int Row = 0;
    for (int i = 0; i < N; i++)
    {
        int sum = 0;
        for (int j = 0; j < M; j++)
        {
            sum = sum + Matrix[i][j];
        }
        if (Row < sum)
        {
            Row = sum;
        }
    }
    int Column = 0;
    for (int i = 0; i < M; i++)
    {
        int sum = 0;
        for (int j = 0; j < N; j++)
        {
            sum = sum + Matrix[j][i];
        }
        if (Column < sum)
        {
            Column = sum;
        }
    }
    int sum = Row + Column;
    cout << sum;
    
    return 0;
}

Python

R,C=[],[]   
m=int(input())
n=int(input())
arr=[]
for i in range(m):
    arr.append(list(map(int,input().split())))
#finding sum of each row
for i in range(m):
    sum=0
    for j in range(n):
        sum += arr[i][j]
    R.append(sum)
#finding sum of each column
for i in range(m) :
    sum=0
    for j in range(n) :
        sum += arr[j][i]
        C.append(sum)
print(max(R)+max(C))

Question 8

Williamson is an analyst he needs to analyse a particular topic for performing analysis for that he needs to find a permutation of a given object.He don’t know how to find permutation so for simplifying his work he is hiring one software developer who can code for him and find a permutation and combination of a given object.

Consider you are giving an interview to williamson for working with him. Find a permutation of given input to proof that you are fit for his requirement.

Input Specification:
nCr where n and r are numbers given by Williamson to you
nCr is defined as n! / (r! x (n-r)!)

Here, n! denotes the factorial of a number. Also, you have to calculate this number as modulo
Input Specification:

input1: The number n.
Input2: The number r.
Input3: The number m,
.

Output specification:

The value of nCr%m.

Example 1:
Input1: 3
Input2: 2
Input3: 10000000009

Output:3

Explanation:
n=3.r=2,m=100 So, n!=3!=6, r!=2!=2, (n-1)!= 1!=1.
So, nCr = (6/(2*1))%1000000009= 3.

Example 2:
input1: 5
input2: 2
input3: 1000000009

Output: 10

Explanation:
n=5,r=2, m=100 So, n!=5!=120, r!=2=2, (n-1)!= 3!=6.
So, nCr = (120/(2*6))%1000000009= 10.

Java

Python

Java

import java.util.*;
public class Main {
  static int fact(int number) {
    int f = 1;
    int j = 1;
    while (j <= number) {
      f = f * j;
      j++;
    }
    return f;
  }

  public static void main(String args[]) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int r = sc.nextInt();
    long m = sc.nextLong();
    int result = fact(n) / (fact(r) * fact(n - r));
    long finalresult = (long) result % m;
    System.out.println("" + result);
  }
}

Python

import math
n=int(input())
r=int(input())
m=int(input())
#nCr= (n!)/((n-r)!)*(r!)
numerator=(math.factorial(n))
denominator=(math.factorial(n-r))*math.factorial(r)
ncr=numerator//denominator
print(ncr%m)

Question 9

A Derangement is a permutation of n elements, such that no element appears in its original position.
For example, a derangement of {0, 1, 2, 3} is {2, 3, 1, 0}.
Given a number n, find the total number of Derangements of a set of n elements.

Input Specification:
input1: N, the number of Objects

Output Specification:
Return the number of arrangements in which no object occurs at its original
position

Example 1:

Input: n = 2
Output: 1
For two elements say {0, 1}, there is only one possible derangement {1, 0}

Example 2:

Input: n = 3
Output: 2
For three elements say {0, 1, 2}, there are two possible derangements {2, 0, 1} and {1, 2, 0}

Example 3:

Input: n = 4
Output: 9
For four elements say {0, 1, 2, 3}, there are 9 possible derangements {1, 0, 3, 2} {1, 2, 3, 0} {1, 3, 0, 2}, {2, 3, 0, 1}, {2, 0, 3, 1}, {2, 3,1, 0}, {3, 0, 1, 2}, {3, 2, 0, 1} and {3, 2, 1, 0

C++

Java

C++

#include<bits/stdc++.h>>
using namespace std;
int countDer(int n)
{

    // base case
    if (n == 1 or n == 2) {
    return n - 1;
    }
    int a = 0;
    int b = 1;
    // using above recursive formula
    for (int i = 3; i <= n; ++i) {
    int cur = (i - 1) * (a + b);
    a = b;
    b = cur;
    }
    return b;
}
    
    // Driver Code
int main()
{
    int n;
    cin>>n;
    cout << countDer(n);
    return 0;
}

Java

import java.util.*;
import java.io.*;
public class Main {
  static int countDer(int n) {

    if (n == 1 || n == 2) {
      return n - 1;
    }

    int a = 0;
    int b = 1;

    for (int i = 3; i <= n; ++i) {
      int cur = (i - 1) * (a + b);
      a = b;
      b = cur;
    }

    return b;
  }

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    System.out.println("" + countDer(n));

  }
}

Question 10

Vira writes an apology letter to anu. However, before Anu can read it, Vira’s enemy Rohan takes it and rotates the characters of each word left to right N times. Find the number of words that remain the same even after this shifting of letters.

Input Specification:

input1: String of words
input2: N, number of times rotation happens

Output Specification:

Your function should return the number of correct words.

Example 1:

input1: llohe ereth
input2: 2

Output : 2

Example 2:

input1: Sorry
input2: 2

Output : 0

C++

Java

C++

#include<bits/stdc++.h>
using namespace std;
// In-place rotates s towards left by d
void leftrotate(string &s, int d)
{
    reverse(s.begin(), s.begin()+d);
    reverse(s.begin()+d, s.end());
    reverse(s.begin(), s.end());
}
// Driver code
int main()
{
    string str1;
    cin>>str1;
    Int n;
    cin>>n;
    leftrotate(str1, n);
    cout << str1 << endl;
    
    return 0;
}

Java

import java.util.*;
import java.io.*;
public class Apology {

  static String leftrotate(String str, int d) {
    String ans = str.substring(d) + str.substring(0, d);
    return ans;
  }

  public static void main(String args[]) {
    Scanner sc = new Scanner(System.in);
    String str1 = sc.nextLine();
    int n = sc.nextInt();
    String rotate = leftrotate(str1, n);
    char ch1[] = str1.toCharArray();
    char ch2[] = rotate.toCharArray();

    int count = 0;
    for (int i = 0; i < str1.length(); i++) {
      if (ch1[i] == ch2[i])
        count++;
    }

    System.out.print("" + count);
  }
}

Question 11

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

C++

Java

C++

#include<bits/stdc++.h> 
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;
}

Java

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));
  }
}