Intro to Discrete Math With C++

Maths ( especially discrete mathematics ) and computer science go very much hand in hand.

Factorization

The factor of a number, N is a number d such that d divides N.
That is, N % d == 0.

Example:

For number 6, the factors are 1, 2, 3 and 6.

Question 1: All Factors

Given a number N, find all factors of N.

N = 6
factors = {1, 2, 3, 6}

Solution

Time Complexity: O(sqrt(n))

Question 2: Verify Prime

Given a number N, verify if N is prime or not.

Solution

Time Complexity: O(sqrt(n))

Question 3: Find all primes

Given a number N, find all prime numbers up to N ( N included ).

If N = 7,

all primes till 7 = {2, 3, 5, 7}

Solution: Sieve of Eratosthenes

Time Complexity: O(n*log(log n))

Base Number System

In our customary base-ten system, we have digits for the numbers zero through nine. We do not have a single-digit numeral for “ten”. Yes, we write “10”, but it's two digits; we have no single solitary digit that stands for “ten”.

There are 10 digits using which we represent all the numbers. Hence the base 10 system.

Similarly, a binary number system or base 2 number system has only 2 digits 0, 1. Hex number system or base 16 number system has 16 digits ( 0, 1, 2 .. 9, A, B, .. F ). In general, an N base number system has N digits, 0, 1, ... N-1 ( The digits usually after 9 are represented as A, B, and so on ).

Base systems like binary and hexadecimal seem a bit strange at first. The key is understanding how different systems “tick over” like an odometer when they are full.

Base 10, our decimal system, “ticks over” when it gets 10 items, creating a new digit. We wait 60 seconds before “ticking over” to a new minute. Hexadecimal and binary are similar, but tick over every 16 and 2 items, respectively.

In computers, numbers are internally represented in the binary number system.

Unary Number System

Way back in the day, we didn’t have base systems! It was uphill both ways, through the snow and blazing heat. When you wanted to count one, you’d write:

|

When you wanted 5, you’d write

|||||

And clearly, 1 + 5 = 6

| + ||||| = ||||||

This is the simplest way of counting.

The value of any number = number of |’s

Binary Number System

Unary, where we just write 1, 11, 111… just goes on forever. Binary, with two options (1 and 0) looks like this:

1: 1
2: 10 (we’re full – tick over)
3: 11
4: 100 (we’re full again – tick over)
5: 101
6: 110
7: 111
8: 1000 (tick over again)

and so on …

Now, how do we convert an arbitrary binary number to its decimal equivalent? Obviously counting and matching is not an option.

Let us first look at the value of 10000...n times ( 1 followed by n 0s ):

This number will only come after we have tried all possible n digit numbers in the binary system which has:

2 * 2 * 2 * .. n times possibilities  ( every position can either have 0 or 1 ) 
   =  2^n possibility which covers numbers from 0 to 2^n - 1.

So, the value of 1000..n times = 2n.

Now any number like 1010110 can be expressed as 1000000 + 10000 + 100 + 10 = 2^6 + 2^4 + 2^2 + 2^1.

Hence, if the binary representation is An An-1 An-2 ... A1 A0, then the corresponding value is

A0 * 2^0 + A1 * 2^1 + A2 * 2^2 + .... + An * 2^n

Now, look at the reverse process. Which is given a decimal number N, how do we convert it to binary?
To do this conversion, we need to divide repeatedly by 2, keeping track of the remainders as we go. Watch below:
Let us say our number is 357.

Thus the number converts to 101100101

Question 4: Binary Representation

Given a number N >= 0, find its representation in binary.

if N = 6, binary form = 110

Solution:

Base Conversions For Base N

A base N number system has N digits. The process of conversion of N based number to decimal and vice versa is very similar to the binary number system process we just saw.

The only thing that changes is that 2 is replaced by N.
So, if the N based number system representation is An An-1 ... A2 A1 A0, then the corresponding decimal value is

A0 * N^0 + A1 * N^1 + A2 * N^2 + ...

The reverse process is also exactly similar. We keep dividing by N, keeping track of the remainders as we go.

Let us say our number is 357, and N = 7.

1       R0
             ---------
           7 |  7       R2
             ---------
           7 |  51      R0
             ---------
           7 |  357

Thus the number converts to 1020 in base 7.

Prime Factorization

Time Complexity: O(n^(1/2))

Worst Case: n is a prime number

Number Theory Questions

Question 5: Greatest Common Divisor

Given 2 non-negative integers m and n, find gcd(m, n)

GCD of 2 integers m and n is defined as the greatest integer g such that g is a divisor of both m and n.
Both m and n fit in a 32 bit signed integer.

m : 6
n : 9
GCD(m, n) : 3

Solution: Euclid’s Algorithm

Lets say g is gcd(m, n) and m > n.

m = g * m1
n = g * m2

m - n = g * (m1 - m2)

gcd (m, n) = gcd(m-n, n)

           = gcd(m - 2n, n) if m >= 2n
           = gcd(m - 3n, n) if m >= 3n 
             .
             .
             .
           = gcd(m - k*n, n) if m >= k*n
           
       In other words, we keep subtracting n till the result is greater than 0. Ultimately we will end up with m % n.
       
              So gcd(m, n)  = gcd(m % n, n)
int Solution::gcd(int m, int n) {
         
        if(m < n)
               swap(m, n);
        
        if(n == 0)
               return m;
         

        return gcd(m % n, n);
  }

Question 6: Trailing Zeros in Factorial

Given an integer A, return the number of trailing zeroes in A!.

Example Input

Input 1:

A = 4

Input 2:

A = 5

Example Output

Output 1:

0

Output 2:

1

Example Explanation

Explanation 1:

4! = 24

Explanation 2:

5! = 120

Solution:

The idea is:

The ZERO comes from 10.

The 10 comes from 2 x 5

And we need to account for all the products of 5 and 2, like 4×5 = 20 …

So, if we take all the numbers with 5 as a factor, we will have plenty of even numbers to pair with them to get factors of 10

Example 1:

How many multiples of 5 are there between 1 and 23?

These are 5, 10, 15, and 20, for four multiples of 5. Paired with 2s from the even factors, this makes for four factors of 10, so: 23! has 4 zeros.

Example 2:

How many multiples of 5 are there in the numbers from 1 to 100?

Because 100 ÷ 5 = 20, so, there are twenty multiples of 5 between 1 and 100.

But wait, actually 25 is 5×5, so each multiple of 25 has an extra factor of 5, e.g. 25 × 4 = 100，which introduces an extra of zero.

So, we need to know how many multiples of 25 are there between 1 and 100? Since 100 ÷ 25 = 4, there are four multiples of 25 between 1 and 100.

Finally, we get 20 + 4 = 24 trailing zeroes in 100!

The above examples tell us that we need to care about 5, 5×5, 5×5×5, 5×5×5×5 …

Example 3:

For given number 4617.

5¹ : 4617 ÷ 5 = 923.4, so we get 923 factors of 5

5² : 4617 ÷ 25 = 184.68, so we get 184 additional factors of 5

5³ : 4617 ÷ 125 = 36.936, so we get 36 additional factors of 5

5⁴ : 4617 ÷ 625 = 7.3872, so we get 7 additional factors of 5

5⁵ : 4617 ÷ 3125 = 1.47744, so we get 1 more factor of 5

5⁶ : 4617 ÷ 15625 = 0.295488, which is less than 1, so stop here.

Therefore, 4617! has 923 + 184 + 36 + 7 + 1 = 1151 trailing zeroes.

int trailingZeroes(int n) {
        int sum = 0;
        while (n / 5 > 0) {
            sum += (n / 5);
            n /= 5;
        }
        return sum;
    }

Combinatorics Questions

Question 7: Grid Unique Paths

A robot is located at the top-left corner of an A x B grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?

Example:

Input : A = 2, B = 2
Output : 2
2 possible routes : (0, 0) -> (0, 1) -> (1, 1) 
              OR  : (0, 0) -> (1, 0) -> (1, 1)

Solution:

Note that you have to take m + n — 2 steps in total. You have to take (m — 1) steps going down and (n-1) steps going right.

Let 0 denote a down step and 1 denote a right step.

So we need to find out the number of strings of length m + n — 2 which have exactly m — 1 zeroes and n — 1 ones.

Essentially we need to choose the positions of ‘1s’, and then ‘0s’ fall into the remaining positions.

So, the answer becomes Choose(m+n-2, n — 1).

Note: Calulating (m+n)! would cross even long long int even for small numbers.

int uniquePaths(int m, int n) {
            // m+n-2 C n-1 = (m+n-2)! / (n-1)! (m-1)! 
            long long ans = 1;
            for (int i = n; i < (m + n - 1); i++) {
                ans *= i;
                ans /= (i - n + 1);
            }
            return (int)ans;
        }

Number Encoding Questions

Question 8: Next Similar Number

Given a number A in a form of string.

You have to find the smallest number that has same set of digits as A and is greater than A.

If A is the greatest possible number with its set of digits, then return -1.

Problem Constraints

1 <= A <= 10100000

A doesn’t contain leading zeroes.

Input Format

First and only argument is an numeric string denoting the number A.

Output Format

Return a string denoting the smallest number greater than A with same set of digits , if A is the largest possible then return -1.

Example Input

Input 1:

A = "218765"

Input 2:

A = "4321"

Example Output

Output 1:

"251678"

Output 2:

"-1"

Example Explanation

Explanation 1:

The smallest number greater then 218765 with same set of digits is 251678.

Explanation 2:

The given number is the largest possible number with given set of digits so we will return -1.

Solution:

Following are few observations about the next greater number.

1. If all digits sorted in descending order, then output is always “Not Possible”. For example, 4321.
2. If all digits are sorted in ascending order, then we need to swap last two digits. For example, 1234.
3. For other cases, we need to process the number from rightmost side (why? because we need to find the smallest of all greater numbers)

Following is the algorithm for finding the next greater number.

1. Traverse the given number from rightmost digit, keep traversing till you find a digit which is smaller than the previously traversed digit. For example, if the input number is “534976”, we stop at 4 because 4 is smaller than next digit 9. If we do not find such a digit, then output is “Not Possible”.
2. Now search the right side of above found digit ‘d’ for the smallest digit greater than ‘d’. For “534976″, the right side of 4 contains “976”. The smallest digit greater than 4 is 6.
3. Swap the above found two digits, we get 536974 in above example.
4. Now sort all digits from position next to ‘d’ to the end of number. The number that we get after sorting is the output. For above example, we sort digits in bold 536974. We get “536479” which is the next greater number for input 534976.

The above implementation can be optimized in following ways:

1. We can use binary search in step II instead of linear search.
2. In step 4, instead of doing simple sort, we can apply some clever technique to do it in linear time. Hint: We know that all digits are linearly sorted in reverse order except one digit which was swapped.

With above optimizations, we can say that the time complexity of this method is O(len(A)).

Digit Operation Questions

Question 9: Palindrome Integer

Determine whether an integer is a palindrome. Do this without extra space.

A palindrome integer is an integer x for which reverse(x) = x where reverse(x) is x with its digit reversed.
Negative numbers are not palindromic.

Example :

Input : 12121
Output : True
Input : 123
Output : False

Solution:

If you are thinking of converting the integer to string, note the restriction of using extra space.

Try reversing the integer.

int reverse(int A) {
    int rev=0;
    while(A>0) {
        rev=rev*10+A%10;
        A=A/10;
    }
return rev;
}

int isPalindrome(int A) {
   return A==reverse(A);
}

Question 10: Reverse Integer

Reverse digits of an integer.

Example1:

x = 123,

return 321
Example2:

x = -123,

return -321

Solution:

1) num % 10 gives you the last digit of a number.

2) num / 10 gives you the number after removing the last digit.

3) num * 10 + digit appends the digit at the end of the number.

int reverse(int x) {
    // solution without using strings
    int rev = 0, sign = 1, digit;
    if (x < 0) {
        sign = -1;
        x *= -1;
    }
    while (x > 0) {
        digit = x%10;
        // check for overflow here 
        if (rev > (INT_MAX / 10) || (rev == (INT_MAX / 10) && digit > (INT_MAX % 10))) {
            return 0;
        }
        rev = rev * 10 + digit;
        x/=10;
    }
    rev *= sign;        
        return rev;
    }

Miscellaneous Questions

Question 11: Total Moves For Bishop!

Given the position of a Bishop (A, B) on an 8 * 8 chessboard.

Your task is to count the total number of squares that can be visited by the Bishop in one move.

The position of the Bishop is denoted using row and column number of the chessboard.

Problem Constraints

1 <= A, B <= 8

Input Format

First argument is an integer A denoting the row number of the bishop.

Second argument is an integer B denoting the column number of the bishop.

Output Format

Return an integer denoting the total number of squares that can be visited by the Bishop in one move.

Example Input

Input 1:

A = 4
B = 4

Example Output

Output 1:

13

Solution:

In the game of chess, a Bishop can only move diagonally and there is no restriction in distance for each move.

So, We can also say that Bishop can move in four ways i.e. diagonally top left, top right, bottom left and bottom right from current position.

We can calculate the numbers of squares visited in each move by:

Total squares visited in Top Left move = min(A,B) — 1
Total squares visited in Top Right move = min(A, 9 — B) — 1
Total squares visited in Bottom Left move = 8 — max(A, 9 — B)
Total squares visited in Bottom Right move = 8 — max(A, B)

where, A and B are the coordinates of the current position of the Bishop on the chessboard.

Question 12: Distribute in Circle!

A items are to be delivered in a circle of size B.

Find the position where the Ath item will be delivered if we start from a given position C.

NOTE: Items are distributed at adjacent positions starting from C.

Problem Constraints

1 <= A, B, C <= 108

Input Format

First argument is an integer A.

Second argument is an integer B.

Third argument is an integer C.

Output Format

Return an integer denoting the position where the Ath item will be delivered if we start from a given position C.

Example Input

Input 1:

A = 2
B = 5
C = 1

Input 2:

A = 8
B = 5
C = 2

Example Output

Output 1:

2

Output 2:

4

Example Explanation

Explanation 1:

The first item will be given to 1st position. Second (or last) item will be delivered to 2nd position

Explanation 2:

The last item will be delivered to 4th position

Solution:

We check if the number of items to be distributed is greater than our remaining positions in current cycle of circle or not.

If yes, then we simply return A + C — 1 (We distribute items in same cycle starting from C). Else we compute number of remaining items after completing current cycle and return mod of remaining items.

int solve(int A, int B, int C) {
int a=(A+C-1)%B;
if(a==0)
  {return B;}
else
  {return a;}
}

Question 13: FizzBuzz

Given a positive integer A, return an array of strings with all the integers from 1 to N.
But for multiples of 3, the array should have “Fizz” instead of the number.
For the multiples of 5, the array should have “Buzz” instead of the number.
For numbers that are multiples of 3 and 5 both, the array should have “FizzBuzz” instead of the number.

Look at the example for more details.

Example

A = 5
Return: [1 2 Fizz 4 Buzz]

Solution:

While Iterating from 1 to N, you need to check the following conditions in sequence:

• Check whether the number is divisible by 3 and 5, if that is the case, print FizzBuzz.
• Check whether the number is divisible by 3, in that case, print Fizz.
• Next, check whether the number is divisible by 5, in that case, print Buzz.
• Otherwise, print the number.

Time Complexity: O(N)
Space Complexity: O(1)

vector<string> Solution::fizzBuzz(int A) {
    
    vector<string>solution;
    for(int i=1;i<=A;i++){
        if(i%3==0 && i%5==0){
            solution.push_back("FizzBuzz");
        }
        else if(i%3==0)
        solution.push_back("Fizz");
        else if(i%5==0)
        solution.push_back("Buzz");
        else
        solution.push_back(to_string(i));
    }
    return solution;
    
}

Question 12: Is Rectangle?

Given four positive integers A, B, C, D, determine if there’s a rectangle such that the lengths of its sides are A, B, C, and D (in any order).

If any such rectangle exists return 1 else return 0.

Problem Constraints

1 <= A, B, C, D <= 100

Input Format

The first argument is an integer A.

The second argument is an integer B.

The third argument is an integer C.

The fourth argument is an integer D.

Output Format

If any such rectangle exist whose sides are A, B, C, D in any orde then return 1 else return 0.

Example Input

Input 1:

A = 1
B = 1
C = 2
D = 2

Input 2:

A = 1
B = 2
C = 3
D = 4

Example Output

Output 1:

1

Output 2:

0

Example Explanation

Explanation 1:

The rectangle drawn above is one of the rectangles that can be formed by side length of 1, 1, 2, 2 so we will return 1.

Explanation 2:

No such rectangle exist whose sides are 1, 2, 3, 4. So, we will return 0.

Solution:

As in a rectangle, Two opposite sides of the rectangle are equal, So, we will check, if any of the two integers are equal and make sure rest of two are also equal using few if else conditions.

Also keep in mind that Square is also a rectangle.
Time Compexity: O(1)

int Solution::solve(int A, int B, int C, int D) {
    /* A rectangle has 4 sides and if any 2 are equal,
    *  then other 2 must be equal as well.
    *  So pick any 2 among 4 is 4C2 = 6.
    *  Check 6 conditions and you done.
    Simple solution.
    */
    if(A == B) return C == D;
    else if(A == C) return B == D;
    else if(A == D) return B == C;
    else return false;
    
}

Author: https://www.linkedin.com/in/shivam-ross/ | https://twitter.com/BeastofBayArea | https://www.instagram.com/sup.its.shiv/