Problem Given an amount of money in US currency. Give an algorithm to make change of the given amount using the smallest possible number of coins. Recall that US coins are Dollars (100 cents), Quarters (25 cents), Dimes (10 cents), Nickels (5 cents) and Pennies (1 cent) Solution A greedy approach to solve this problem
Given a sorted array of (n) integers that has been rotated an unknown number of times. Give a log(n) algorithm that finds an element in the array. Assume the array has no duplicates.
Maximum of two numbers without comparison Write a C++ function which takes two positive integers x and y as input then return x if x > y otherwise return y. Assume x is not equal to y. You are not allowed to use any comparison operator or any if statement. Solution: maximum of two numbers
Pairs with sum problem Given an array of integers A[N]. Find all pairs of integers in the array which sum to a given value (v) Solution Let us try to solve this problem using brute force approach Code for sum of pairs method Here is the code in Perl This is not an efficient solution
Array shuffle algorithm Given an array of 2n integers in the following format a1 a2 a3 … an b1 b2 b3 … bn. Rearrange the array as follows a1 b1 a2 b2 a3 b3 … an bn taking into consideration the following restrictions: 1. Arrange the array in place i.e. do not use any additional
Problem Given an array of N integers. The array is expected to contain positive as well as negative numbers. Find the maximum contiguous subsequence sum (MCSS) of the array. For example the MCSS of {2, -4, 1, 2} is 3 which is the sum of the subsequence {1, 2}. A brute force approach requires 3
Maximum contiguous subsequence sum problem Given an array of N integers. The array is expected to contain positive as well as negative numbers. Find the maximum contiguous subsequence sum (MCSS) of the array. For example the MCSS of {2, -4, 1, 2} is 3 which is the sum of the subsequence {1, 2}. A brute
Fibonacci numbers problem Write a program to compute the Fibonacci sequence number of a given integer. Your algorithm must run in linear time ie O(N). What is the fibonacci sequence Definition: Fibonacci number of (N) is the sum of Fibonacci numbers of (N-1) and (N-2). In other words, the fibonacci numbers list formula: where Fibonacci
String to integer in c++ Given an integer number in string format, for example “12345”. Write a program or function to convert a string to integer in C without using library. String to integer algorithm Loop through the characters of the string representing the integer number. Get the integer value of the current digit by
Greatest common factor problem Given two integers A less than B. Write code to find the greatest common divisor between A and B commonly known as GCD. What is a greatest common factor GCD(A, B) is the largest positive integer that divides A and B without a remainder. We can loop starting at 2 ending