Tag Archives: C / C++

Euler’s Totient Function

Euler Function: In number theory, Euler’s totient function (or Euler’s phi function), denoted as φ(n) or ϕ(n), is an arithmetic function that counts the positive integers less than or equal to n that are relatively prime to n , i.e., the numbers whose GCD (Greatest Common Divisor) with n is 1. (These integers are sometimes Read More →

Euclid’s Algorithm (Greatest Common Divisor) – GCD

Given two non-negative integers a and b. We need to find their greatest common divisor (GCD), ie, the largest number that divides both a and b. When it is of the numbers is zero, and the other is non-zero, their greatest common divisor, by definition, it is the second number. When both numbers are zero, Read More →

How to Check if a given Number is Fibonacci number?

In mathematics, the Fibonacci numbers or Fibonacci sequence are the numbers in the following integer sequence: 1,1,2,3,5,8,13,21,34,55,89,144.. A simple way is to generate Fibonacci numbers until the generated number is greater than or equal to ‘x’. Following is an interesting property about Fibonacci numbers that can also be used to check if a given number Read More →

Product of All Other Array Numbers

Problem: Given an array of n integers where n>1, return an array of same size an input array where at every index of the output array should contain the product of all elements in the array except the element at the given index. Example: arr[] = {10, 4, 1, 6, 2} prod[] = {48,120,480,80,240} Solution: Read More →

Macros vs Functions

Macros are pre-processed which means that all the macros would be processed before your program compiles. However, functions are not preprocessed but compiled. See the following example of Macro: Output: 10 See the following example of Function: Output: 10 In short, Macro features: Macro is Preprocessed No Type Checking Code Length Increases Use of macro Read More →

Pascal’s Triangle

Given numRows, generate the first numRows of Pascal’s triangle. For example, given numRows = 5, Return [ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ] The logic becomes apparent just by looking at the pattern, but the property of pascal’s triangle comes from coefficients in the binomial expansion. nCk = n-1Ck + n-1Ck-1 and nC0 =1

Write Power Function without using multiplication(*) and division(/) operators

Write your own Power function without using multiplication(*) and division(/) operators? (Using Nested Loops) We can calculate power by using repeated addition. For example to calculate 5^4. 1) First 5 times add 5, we get 25. (5^2) 2) Then 5 times add 25, we get 125. (5^3) 3) Then 5 time add 125, we get Read More →

Find Seed of a Number

A number X is said to be ‘seed’ of number Y if multiplying X by its digit equates to Y. For example, 123 is a seed of 738 coz 123*1*2*3 = 738. Now given a number find all its ‘seed’. Solution:

Number of Trailing Zeros in Factorial of a Number

Write a program to output the number of consecutive trailing zeros in the factorial of a number? Solution: 1. The number of trailing zeros in a number is equivalent to the power of 10 in the factor of that number. 2. The number power of 10 in the factors is the same as the minimum Read More →

Largest Difference in an Array

You have an array of integers: int[] A = { 10, 3, 6, 8, 9, 4, 3 }; My goal is to find the largest difference between A[Q] and A[P] such that Q > P. If P = 1 and Q = 4 diff = A[Q] – A[P] diff = 9 – 3 diff = Read More →

Minimum Distance Between Array Elements

Given a non-negative integer array, Find the minimum distance between 2 distinct elements of A. Minimum Distance is defined as if P != Q then |(A[P] – A[Q])| Solution: Time Complexity: O(N)

Passing Car East or West Codility

A non-empty zero-indexed array A consisting of N integers is given. The consecutive elements of array A represent consecutive cars on a road. Array A contains only 0s and/or 1s: 0 represents a car traveling east, 1 represents a car traveling west. The goal is to count passing cars. We say that a pair of Read More →