Greedy Algorithm to find Minimum number of Coins
Given a value V, if we want to make change for V Rs, and we have infinite supply of each of the denominations in Indian currency, i.e., we have infinite supply of { 1, 2, 5, 10, 20, 50, 100, 500, 1000} valued coins/notes, what is the minimum number of coins and/or notes needed to make the change?
Examples:
Input: V = 70
Output: 2
We need a 50 Rs note and a 20 Rs note.
Input: V = 121
Output: 3
We need a 100 Rs note, a 20 Rs note and a
1 Rs coin.
We strongly recommend you to minimize your browser and try this yourself first.
The idea is simple Greedy Algorithm. Start from largest possible denomination and keep adding denominations while remaining value is greater than 0. Below is complete algorithm.
1) Initialize result as empty.
2) find the largest denomination that is
smaller than V.
3) Add found denomination to result. Subtract
value of found denomination from V.
4) If V becomes 0, then print result.
Else repeat steps 2 and 3 for new value of V
Below is C++ implementation of above algorithm.
// C++ program to find minimum number of denominations
#include <bits/stdc++.h>
using namespace std;
// All denominations of Indian Currency
int deno[] = {1, 2, 5, 10, 20, 50, 100, 500, 1000};
int n = sizeof(deno)/sizeof(deno[0]);
// Driver program
void findMin(int V)
{
// Initialize result
vector<int> ans;
// Traverse through all denomination
for (int i=n-1; i>=0; i--)
{
// Find denominations
while (V >= deno[i])
{
V -= deno[i];
ans.push_back(deno[i]);
}
}
// Print result
for (int i = 0; i < ans.size(); i++)
cout << ans[i] << " ";
}
// Driver program
int main()
{
int n = 93;
cout << "Following is minimal number of change for " << n << " is ";
findMin(n);
return 0;
}
Output:
Following is minimal number of change for 93 is 50 20 20 2 1
Note that above approach may not work for all denominations. For example, it doesn’t work for denominations {9, 6, 5, 1} and V = 11. The above approach would print 9, 1 and 1. But we can use 2 denominations 5 and 6.
For general input, we use below dynamic programming approach.
Find minimum number of coins that make a given value
Thanks to Utkarsh for providing above solution here.
===========================================================================
Find the largest three elements in an array
Given an array with all distinct elements, find the largest three elements. Expected time complexity is O(n) and extra space is O(1).
Examples:
Input: arr[] = {10, 4, 3, 50, 23, 90}
Output: 90, 50, 23
Source: http://qa.geeksforgeeks.org/1019/array-number-elements-given-largest-numbers-array-sorting
We strongly recommend you to minimize your browser and try this yourself first.
Below is algorithm:
1) Initialize the largest three elements as minus infinite.
first = second = third = -∞
2) Iterate through all elements of array.
a) Let current array element be x.
b) If (x > first)
{
// This order of assignment is important
third = second
second = first
first = x
}
c) Else if (x > second)
{
third = second
second = x
}
d) Else if (x > third)
{
third = x
}
3) Print first, second and third.
Below is C implementation of above algorithm.
#include <stdio.h>
#include <limits.h> /* For INT_MIN */
/* Function to print three largest elements */
void print2largest(int arr[], int arr_size)
{
int i, first, second, third;
/* There should be atleast two elements */
if (arr_size < 3)
{
printf(" Invalid Input ");
return;
}
third = first = second = INT_MIN;
for (i = 0; i < arr_size ; i ++)
{
/* If current element is smaller than first*/
if (arr[i] > first)
{
third = second;
second = first;
first = arr[i];
}
/* If arr[i] is in between first and second then update second */
else if (arr[i] > second)
{
third = second;
second = arr[i];
}
else if (arr[i] > third)
third = arr[i];
}
printf("Three largest elements are %d %d %d\n", first, second, third);
}
/* Driver program to test above function */
int main()
{
int arr[] = {12, 13, 1, 10, 34, 1};
int n = sizeof(arr)/sizeof(arr[0]);
print2largest(arr, n);
return 0;
}
Output:
Three largest elements are 34 13 12
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
==============================================================================
Find if a point lies inside a Circle
Given a circle (coordinates of centre and radius) and a point (coordinate), find if the point lies inside or on the circle, or not.
Examples:
Input: x = 4, y = 4 // Given Point
circle_x = 1, circle_y = 1, rad = 6; // Circle
Output: Inside
Input: x = 3, y = 3 // Given Point
circle_x = 0, circle_y = 1, rad = 2; // Circle
Output: Outside
We strongly recommend you to minimize your browser and try this yourself first.
The idea is compute distance of point from center. If distance is less than or equal to radius. the point is inside, else outside.
Below is C++ implementation of above idea.
// C++ program to check if a point lies inside a circle or not
#include<iostream>
using namespace std;
bool isInside(int circle_x, int circle_y, int rad, int x, int y)
{
// Compare radius of circle with distance of its center from
// given point
if ((x - circle_x)*(x - circle_x) +
(y - circle_y)*(y - circle_y) <= rad*rad)
return true;
else
return false;
}
// Driver function
int main()
{
int x = 1, y = 1;
int circle_x = 0, circle_y = 1, rad = 2;
isInside(circle_x, circle_y, rad, x, y)?
cout << "Inside": cout << "Outside";
}
Outside:
Inside
Thanks to Utkarsh Trivedi for suggesting above solution
================================================================================
Check if a sorted array can be divided in pairs whose sum is k
Given a sorted array of integers and a number k, write a function that returns true if given array can be divided into pairs such that sum of every pair k.
Expected time complexity O(n) and extra space O(1). This problem is a variation of below problem, but has a different interesting solution that requires only O(1) space.
Check if an array can be divided into pairs whose sum is divisible by k
Examples:
Input: arr[] = {1, 3, 3, 5}, k = 6
Output: True
We can divide array into (1, 5) and (3, 3).
Sum of both of these pairs is 6.
Input: arr[] = {2, 5, 5, 5, 5, 8}, k = 10
Output: True
We can divide array into (2, 8), (5, 5) and
(5, 5). Sum of all these pairs is 10.
We strongly recommend you to minimize your browser and try this yourself first.
A Simple Solution is to iterate through every element arr[i]. Find if there is another not yet visited element with value (k – arr[i]). If there is no such element, return false. If a pair is found, then mark both elements as visited. Time complexity of this solution is O(n2 and it requires O(n) extra space.
A Better Solution is to use Hashing. Solution given on this post can be easily modified to work. Time complexity of this solution is O9n) but it requires extra space for hash table.
An Efficient Solution is to use Meet in the Middle algorithm discussed in method 1 here.
1) Initialize two index variables
(a) Initialize first to the leftmost index: l = 0
(b) Initialize second the rightmost index: r = n-1
2) Loop while l < r.
(a) If (A[l] + A[r] != k) then return false
(b) Else r--, l++
Below is C++ implementation of above algorithm.
// A C++ program to check if arr[0..n-1] can be divided
// in pairs such that every pair has sum k.
#include <bits/stdc++.h>
using namespace std;
// Returns true if arr[0..n-1] can be divided into pairs
// with sum equal to k.
bool canPairsSorted(int arr[], int n, int k)
{
// An odd length array cannot be divided into pairs
if (n & 1)
return false;
// Traverse from both sides of array
int l = 0, r = n-1;
while (l < r)
{
// If array can be divided, then sum of current
// elements must be sum
if (arr[l] + arr[r] != k)
return false;
// Move index variables
l++; r--;
}
return true;
}
/* Driver program to test above function */
int main()
{
int arr[] = {1, 2, 3, 3, 3, 3, 4, 5};
int n = 6;
int n = sizeof(arr)/sizeof(arr[0]);
canPairs(arr, n, k)? cout << "True": cout << "False";
return 0;
}
Output:
True
Time Complexity: O(n)
Auxiliary Space: O(1)
This article is contributed by Priyanka.
==================================================================================
Remove recurring digits in a given number
Given a number as string, remove recurring digits from the given string. The changes must be made in-place. Expected time complexity O(n) and auxiliary space O(1).
Examples:
Input: num[] = "1299888833"
Output: num[] = "12983"
Input: num[] = "1299888833222"
Output: num[] = "129832"
We strongly recommend you to minimize your browser and try this yourself first
This problem is similar to Run Length Encoding.
Let num[] be input number represented as character array
1) Initialize index of modified string 'j' as 0.
2) Traverse input string and do following for every digit num[i].
a) Copy current character 'num[i]' to 'num[j]' and increment i & j.
b) Keep incrementing i while num[i] is same as previous digit.
3) Add string termination character at 'num[j]'
Below is C++ implementation of above algorithm.
// C++ program to remove recurring digits from
// a given number
#include <bits/stdc++.h>
using namespace std;
/* Removes recurring digits in num[] */
void removeRecurringDigits(char num[])
{
int len = strlen(num);
int j = 0; // Index in modified string
/* Traverse digits of given number one by one */
for (int i=0; i<len; i++)
{
/* Copy the first occurrence of new digit */
num[j++] = num[i];
/* Remove repeating occurrences of digit */
while (i + 1 < len && num[i] == num[i+1])
i++;
}
/* terminate the modified string */
num[j] = '\0';
}
/* Driver program to test above function */
int main()
{
char num[] = "1299888833";
removeRecurringDigits(num);
cout << "Modified number is " << num;
return 0;
}
Output:
Modified number is 12983
This article is contributed by Priyanka.
==================================================================================
Add two numbers using ++ and/or —
Given two numbers, return sum of them without using operators + and/or -, and using ++ and/or –.
Examples:
Input: x = 10, y = 5
Output: 15
Input: x = 10, y = -5
Output: 10
We strongly recommend you to minimize your browser and try this yourself first
The idea is to do y times x++, if y is positive and do y times x– if y is negative.
// C++ program to add two numbers using ++
#include<bits/stdc++.h>
using namespace std;
// Returns value of x+y without using +
int add(int x, int y)
{
// If y is positive, y times add 1 to x
while (y > 0 && y--)
x++;
// If y is negative, y times subtract 1 from x
while (y < 0 && y++)
x--;
return x;
}
int main()
{
cout << add(43, 23) << endl;
cout << add(43, -23) << endl;
return 0;
}
Output:
76
20
Thanks to Gaurav Ahirwar and human for suggesting above solution here.
============================================================================
Check if two numbers are equal without using arithmetic and comparison operators
Following are not allowed to use
1) Arithmetic and Comparison Operators
2) String functions
We strongly recommend you to minimize your browser and try this yourself first
The ide is to use XOR operator. XOR of two numbers is 0 if the numbers are same, otherwise non-zero.
#include <iostream>
using namespace std;
void areSame(int a, int b)
{
if (a^b) cout << "Not Same";
else cout << "Same";
}
int main()
{
areSame(10, 20);
}
Output:
Not Same
==========================================================================
Program to check if a given number is Lucky (all digits are different)
A number is lucky if all digits of the number are different. How to check if a given number is lucky or not.
Examples:
Input: n = 983
Output: true
All digits are different
Input: n = 9838
Output: false
8 appears twice
We strongly recommend you to minimize your browser and try this yourself first.
The idea is to traverse through every digit of given number and mark
the traversed digit as visited. Since total number of digits is 10, we
need a boolean array of size only 10 to mark visited digits.
Below is C++ implementation of above idea.
// C++ program to check if a given number is lucky
#include<iostream>
using namespace std;
// This function returns true if n is lucky
bool isLucky(int n)
{
// Create an array of size 10 and initialize all
// elements as false. This array is used to check
// if a digit is already seen or not.
bool arr[10];
for (int i=0; i<10; i++)
arr[i] = false;
// Traverse through all digits of given number
while (n > 0)
{
// Find the last digit
int digit = n%10;
// If digit is already seen, return false
if (arr[digit])
return false;
// Mark this digit as seen
arr[digit] = true;
// REmove the last digit from number
n = n/10;
}
return true;
}
// Driver program to test above function.
int main()
{
int arr[] = {1291, 897, 4566, 1232, 80, 700};
int n = sizeof(arr)/sizeof(arr[0]);
for (int i=0; i<n; i++)
isLucky(arr[i])? cout << arr[i] << " is Lucky \n":
cout << arr[i] << " is not Lucky \n";
return 0;
}
Output:
1291 is not Lucky
897 is Lucky
4566 is not Lucky
1232 is not Lucky
80 is Lucky
700 is not Lucky
Time Complexity: O(d) where d is number of digits in input number.
Auxiliary Space: O(1)
This article is contributed by Himanshu.
============================================================================
Program to check if a given number is prime or not
Solution 1:
============
int result = -1;
for(i = 2; i < n-1; i++)
{
if(n/i){
result = 1;
break;
}
}
if(result == 1) { printf(“Number is prime”);
else { printf(“Number is not prime”}
Solution 2:
===========
int result = -1;
for(i = 2; i < sqrt(n); i++)
{
if(n/i){
result = 1;
break;
}
}
if(result == 1) { printf(“Number is prime”);
else { printf(“Number is not prime”}
============================================================================
Program for prime factorisation of a number
PrimeFactorisation(n) {
for(int i=2; i <= sqrt(n) ; i++) {
if( n%i == 0) {
int count = 0;
while( n%i == 0) {
n = n/i;
count++;
}
printf(“ i : %d, count : %d”, i , count);
}
}
}
==============================================================================
Calculate GCD using Euclid's Algorithm:
int euclid_gcd(int a, int b) {
int dividend = (a >= b) ? a : b;
int divisor = (a <= b ) ? a : b;
while (divisor != 0){
int remainder = dividend % divisor;
dividend = divisor;
divisor = remainder;
}
return dividend;
}
====================================================
How many distinct binary search trees can be created out of 4 distinct keys?
Ans:
No. of BST= 2nCn/(n+1)
Therefore 8C4/5 =14
=======================================================
A binary tree T has 20 leaves. The number of nodes in T having two children is ______.
Ans:
In Binary tree If there are N leaf nodes then the number of Nodes having two children will be N-1. So in this case answer will be 20-1, means 19.
=======================================================
*** A complete graph Kn has power(n, n-2) spanning trees.
=======================================================
Simple Graph
A graph with no loops and no parallel edges is called a simple graph.
* The maximum number of edges possible in a single graph with ‘n’ vertices is nC2 where nC2 = n(n – 1)/2.
* The number of simple graphs possible with ‘n’ vertices = 2nc2 = 2n(n-1)/2.
The maximum number of edges with n=3 vertices −
nC2 = n(n–1)/2
= 3(3–1)/2
= 6/2
= 3 edges
The maximum number of simple graphs with n=3 vertices −
2nC2 = 2n(n-1)/2
= 23(3-1)/2
= 23
= 8
=======================================================
Example 1:
Let ‘G’ be a simple graph with nine vertices and twelve edges, find the number of edges in 'G-'.
You have, |E(G)| + |E('G-')| = |E(Kn)|
12 + |E('G-')| = 9(9-1) / 2 = 9C2
12 + |E('G-')| = 36
|E('G-')| = 24
=======================================================
Example 2:
‘G’ is a simple graph with 40 edges and its complement 'G−' has 38 edges. Find the number of vertices in the graph G or 'G−'.
Let the number of vertices in the graph be ‘n’.
We have, |E(G)| + |E('G-')| = |E(Kn)|
40 + 38 = n(n-1)/2
156 = n(n-1)
13(12) = n(n-1)
n = 13
=======================================================
Circuit Rank
Let ‘G’ be a connected graph with ‘n’ vertices and ‘m’ edges. A spanning tree ‘T’ of G contains (n-1) edges.
Therefore, the number of edges you need to delete from ‘G’ in order to get a spanning tree = m-(n-1), which is called the circuit rank of G.
Example 1:
For the graph given in the above example, you have m=7 edges and n=5 vertices.
Then the circuit rank is
G = m – (n – 1)
= 7 – (5 – 1)
= 3
=======================================================
Example 2:
Let ‘G’ be a connected graph with six vertices and the degree of each vertex is three. Find the circuit rank of ‘G’.
By the sum of degree of vertices theorem,
n
∑
i=1 deg(Vi) = 2|E|
6 × 3 = 2|E|
|E| = 9
Circuit rank = |E| – (|V| – 1)
= 9 – (6 – 1) = 4
=======================================================
Euler’s Path
An Euler’s path contains each edge of ‘G’ exactly once and each vertex of ‘G’ at least once. A connected graph G is said to be traversable if it contains an Euler’s path.
Example

Euler’s Path = d-c-a-b-d-e.
=======================================================
Example 3:
Let ‘G’ be a connected planar graph with 20 vertices and the degree of each vertex is 3. Find the number of regions in the graph.
Solution:
By the sum of degrees theorem,
20
∑
i=1 deg(Vi) = 2|E|
20(3) = 2|E|
|E| = 30
By Euler’s formula,
|V| + |R| = |E| + 2
20+ |R| = 30 + 2
|R| = 12
Hence, the number of regions is 12.
=======================================================
No comments:
Post a Comment