Problem Write a C++ program to count the number of 2’s between 0 and (n) where (n) is a positive integer. Solution We need two loops, one goes from 0 to n and the other one examines the number digit by digit. One way to get the decimal digits of a number is to shift
Problem Write a recursive function to compute (x) to the power of (n) where (x) and (n) are positive integers. Your algorithm should run in O(logn) time complexity Solution Use divide and conquer technique. For even values of (n) calculate x^(n/2) and return the square of that as the final result because x^n = x^(n/2)
Problem Write a C++ recursive function to convert a character string into capital letters. Solution Instead of looping in the string character by character we can recursively call a function while advancing an index each time. Once the index reaches the end of the string we stop recursion. Converting a letter into capital case in
Problem Write a recursive function to compute the product of two positive integers. Solution The product of two positive integers (A*B) is nothing but the sum of the first integer (A), (B) times Code Here is the code in C++
Problem Write a recursive algorithm to compute the average of an array of numbers. Solution The average of an array of numbers is the sum of all numbers divided by the total number of elements. It is the same as dividing each number by the total number of elements then adding each division result to
Problem Given a positive integer. Find the number of trailing zeros in the integer’s factorial. For example the factorial of 10 is 3628800 so the algorithm should print 2 Solution Let us start by a simple example. Factorial of 5 = 5 x 4 x 3 x 2 = 5 x 2 x 2 x
Problem Design a simple Java class to implement the concept of a line in the Cartesian plane. Provide a method to test if the line intersects with another line. Solution Two points are enough to define a line in the Cartesian plane so we can use 4 private variables for that. For the intersection we
Problem Given an array of positive integers. Write an iterative version of binary search to find an element in the array Solution Binary search can be easily implemented using recursion due to the divide and conquer nature of the algorithm however we can also do it using iteration. Please refer to the code below for
Problem Given an array of positive integers. Find the n(th) largest element in the array. Solution Sort the array in decreasing order then loop through the sorted array while counting unique elements then stop when the count is equal to (n). In the code below we will assume the array is already sorted. You can
Divide and conquer largest two numbers problem Given an array of integers. Find the first and second largest elements in the array. Use divide and conquer technique. Divide and conquer algorithm largest two elements Simply divide the array into two halves then find the largest two elements in each half. At the end you need