Waste less time on Facebook — follow Brilliant.
×

10 Basic Algorithms Every Programmer Should Know

Many programming problems (especially on Brilliant) often ask one to determine if certain numbers possess unique qualities. Knowing how to implement this in the code is often a challenge and these algorithms come up frequently when dealing with harder programming problems. Try writing the most efficient method to solve the following 10 problems:

  1. Determine the sum of the digits/product of the digits of a particular number
  2. Determine whether a given number is a square number/cube number
  3. Determine whether a given number has unique digits
  4. Determine whether the digits of a number are in ascending/descending order
  5. Determine whether a given number is prime or composite
  6. Determine the prime factorisation for a given number
  7. Determine the number of factors a particular number has
  8. Determine the nth Fibonacci number
  9. Determine the LCM and GCD of two or more given numbers
  10. Reverse the digits of a particular number

By solving these problems, you develop an "arsenal" of useful algorithms.

Another problem I discussed with Sudeep Salgia:

i) Calculate the nth root of a number

POST THE BEST SOLUTIONS

Note by Mark Mottian
2 years, 6 months ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

Here are my solutions in Java. Most of the things are coded by me but some parts are taken from StackOverflow (which are more efficient than my code) -

1) Sum of digits (number is stored as String) -

1
2
for(int i = 0, sum = 0; i < number.length(); i++)
    sum += Character.getNumericValue(number.charAt(i));

Product of digits (number is stored as String) -

1
2
for(int i = 0, product = 1; i < number.length(); i++)
    product *= Character.getNumericValue(number.charAt(i));

2) Determine whether a given number is a square number -

1
2
if(Math.round(Math.sqrt(number)) == Math.sqrt(number))
    //it is a perfect square

Determine whether a given number is a cube number -

1
2
if(Math.round(Math.cbrt(number)) == Math.cbrt(number))
    //it is a perfect cube

3) Determine whether a given number has unique digits (number is stored as String)

1
2
Set<String> set = new HashSet<String>(Arrays.asList(number.split("")));
if(set.size() == number.length()) //true

4) Check if digits are in ascending order -

1
2
3
4
5
6
7
8
9
private static boolean asc(int number){
    int last = number % 10;
    number /= 10;
    for(int n = 0; n < Integer.toString(number).length(); n++){
        if(number % 10 >= last) return false;
        number /= 10;
    }
    return true;
}

Check if digits are in descending order -

1
2
3
4
5
6
7
8
9
private static boolean des(int number){
    int last = number % 10;
    number /= 10;
    for(int n = 0; n < Integer.toString(number).length(); n++){
        if(number % 10 <= last) return false;
        number /= 10;
    }
    return true;
}

5) Prime / Composite test -

1
2
3
4
5
6
7
boolean prime(int n) { //return true if prime and false if composite
    if(n == 2) return true;
    if (n % 2 ==0  || n == 1) return false;
    for(int i = 3; i * i <=n ;i += 2)
        if(n % i == 0) return false;
    return true;
}

6) Prime Factorization -

1
2
3
4
5
6
List<Integer> list = new ArrayList<Integer>();
for(double n = 1; n <= number/2; n++)
    if(number % n == 0 && prime(n)){ //same prime method defined above
        list.add(n);
        number /= n;
    }

7) Number of factors -

1
2
3
for(int i = 2, num = 2; i <= number / 2; i++)
    if(number % i == 0)
        num++;

8) Nth Fibonacci Number -

1
2
3
4
5
6
7
private static int fibonacci(int nth){
    int a = 1, b = 1;
    for(int i = 3; i <= nth; i += 2){
        a += b; b += a;
    }
    return nth % 2 == 0 ? b : a;
}

9) GCD -

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
private static long gcd(long a, long b){ //gcd of two numbers
    while (b > 0){
        long temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

private static long gcd(long[] input){ //gcd of three or more numbers
    long result = input[0];
    for(int i = 1; i < input.length; i++) result = gcd(result, input[i]);
    return result;
}

LCM -

1
2
3
4
5
6
7
8
9
private static long lcm(long a, long b){ //lcm of two numbers
    return a * (b / gcd(a, b)); //same gcd method given above
}

private static long lcm(long[] input){ //lcm of three or more numbers
    long result = input[0];
    for(int i = 1; i < input.length; i++) result = lcm(result, input[i]);
    return result;
}

10) Reverse digits (number is stored as string)-

1
int reversed = Integer.parseInt(new StringBuilder(number).reverse().toString());


Nth root -

1
Math.pow(num, 1.0 / root);


Additionally, I think that having a generalized Josephus problem solver at our disposal won't be bad. Here is my code. I have tested it but it might still be a bit buggy (known bug - it doesn't work if in \(josephus(m, n)\) \(n > m\). I'll fix it later) -

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
private static int josephus(int m, int n){
    List<Integer> list = new ArrayList<Integer>();
    for(int i = 1; i <= m; i++)
        list.add(i);
    int i = n;
    while(list.size() != 1){
        int len = list.size(), rem = 1;
        for(; i <= len; i += n)
            list.remove(i - rem++);
        i = n - (len - (i - n));
        rem = 1;
        print(list);
    }
    return list.get(0);
}

Aryan Gaikwad - 2 years, 6 months ago

Log in to reply

Thanks for the response! Very helpful!

Mark Mottian - 2 years, 6 months ago

Log in to reply

You are welcome :)

Aryan Gaikwad - 2 years, 6 months ago

Log in to reply

For the (6) Prime Factorization : What's max?

Christopher Boo - 2 years, 6 months ago

Log in to reply

Problem 6

This is the simplest solution that I could come up with for finding the prime factorisation of smaller numbers (Python 3.4.1 Solution):

def primeFactorisation(n):
    primeFactors = []
    for x in range(2, (n+1)):
        while (n % x == 0):
            primeFactors.append(x)
            n = n/x
    return primeFactors

Mark Mottian - 2 years, 6 months ago

Log in to reply

By max, I mean number. The code was from my last year's programming assignment and I forgot to rename the max variable to number before posting it here. Thanks for pointing it out.

Aryan Gaikwad - 2 years, 6 months ago

Log in to reply

Ironically, most of the competitive programming problems outside brilliant.org is not "mathematical".

Christopher Boo - 2 years, 6 months ago

Log in to reply

Not necessarily . Have you checked out Project Euler ?

Azhaghu Roopesh M - 2 years, 6 months ago

Log in to reply

Yes, but compare with codeforces, SPOJ, UVa and other informatics olympiad, they are the minority.

Christopher Boo - 2 years, 6 months ago

Log in to reply

@Christopher Boo Yeah , I agree with you . Btw I didn't know of any coding sites other than Codecademy , Talent Buddy and Top Coder . Are the ones listed above worthy of your time if you plan on becoming a programmer ?

Azhaghu Roopesh M - 2 years, 6 months ago

Log in to reply

To determine the sum of digits of a particular number.

  1. Start

  2. Declare integer \( n \) , where \( n \) is the number whose sum of digits is to be found.

  3. Input \( n \),

  4. Initialize variable \( s = 0 \), where \( s \) will store the sum of digits.

  5. For \( n>0\), repeat this procedure

    \( s = s + [n (mod 10 )] \) (% operator in C++)

    \( n = \lfloor \frac{n}{10} \rfloor \)

  6. Print \( s \)

  7. Stop

Shabarish Ch - 2 years, 6 months ago

Log in to reply

This will only work, iff \(n\) is a non-negative integer. But besides negative numbers, there are also real numbers, for instance \(44.65\).

Patrick Engelmann - 2 years, 6 months ago

Log in to reply

To find whether the number is a perfect square by counting the number of factors. (C++ solution)

It makes use of the property that a perfect square has odd number of factors.

  int n, d = 0;
  cout<<"Enter number";
  cin>>n;
  for( int i = 1; i<=n ; i++)
  {
    if( n%i == 0 )
    {
       d+=1;
    }
  }
  cout<<"The number of factors is "<<d;
  if( d%2 == 1)
  {
    cout<<"The number is a perfect square";
  }
  else
  {
    cout<<"The number is not a perfect square";
  }

Shabarish Ch - 2 years, 6 months ago

Log in to reply

The time efficiency of your solution is \(O(n)\), which makes it not suitable for large numbers. The better approach is to see if the square root of the number is an integer.

Pseudocode

if sqrt(n) % 1 == 0 : return true

Christopher Boo - 2 years, 6 months ago

Log in to reply

How is time efficiency determined? What is \( O(n) \) ?

Shabarish Ch - 2 years, 6 months ago

Log in to reply

@Shabarish Ch Basically, time efficiency is determined by seeing how run time increased as your variable gets larger. In this case, it's increasing linearly, hence \(O(n)\), but mine is constant, that is the run time doesn't increase as the number gets larger, so time efficiency is \(O(1)\).

Christopher Boo - 2 years, 6 months ago

Log in to reply

@Christopher Boo I can't help but comment on this, even though it has been a long time. If square root is computed to a floating-point format, it is \(O(1)\) but imprecise and so your code won't work for large \(n\). If it is computed precisely (say, integer square root to avoid handling with infinite decimal digits), it depends on implementation (this is one of the questions asked above); one implementation that I can think of is binary searching, and it takes \(O(\log n \cdot M)\), where \(M\) is the time taken to multiply two \(\log n\)-digit numbers.

Moral: When dealing with large numbers, arithmetic operations can no longer be assumed to be constant time.

Ivan Koswara - 2 years, 2 months ago

Log in to reply

@Christopher Boo Great, I'll try to improve my algorithm and post a new one. Thanks for telling me!!

Shabarish Ch - 2 years, 6 months ago

Log in to reply

@Shabarish Ch Search "Big O Notation". I think there was a note on this here.

Siddhartha Srivastava - 2 years, 6 months ago

Log in to reply

@Siddhartha Srivastava I didn't know it was called that. But now that you have told me, I will search for it. Thanks..

Shabarish Ch - 2 years, 6 months ago

Log in to reply

4.Determine whether the digits of a number are in ascending/descending order

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
START
Read N //N is the given number as an integer
initialize integer variable dx:=0
while (N/10)>0 repeat steps 7 to 11
//start of loop
 initialize integer variable s:=(N/10)%10-N%10
 If (dx*s>=0) then
    dx:=dx+s,N:=N/10
  else
     dx:=0, break from loop
//end of loop
return dx 
STOP

The algorithm returns positive value if number is in desc negative if number is in asc and 0 if number is neither.

Raghav Vaidyanathan - 2 years, 6 months ago

Log in to reply

3.Determine whether a given number has unique digits

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
START
initialize integer array dig[10]
Read N //N is the given number as an integer
initialize integer variable r:=1
while N>0 repeat steps 7 to 11
//start of loop
 initialize integer variable s:=N%10
 If (dig[s]-1) then
    dig[s]:=1,N:=N/10
  else
     r:=0, break from loop
//end of loop
return r
STOP

Raghav Vaidyanathan - 2 years, 6 months ago

Log in to reply

May I question why these are algorithms everybody needs to know?

Log in to reply

Number 10 : Prints the INTEGER in reverse

1
2
3
4
5
6
7
8
9
def revDigits( n ):
    temp = 0
    num = n
    while num:
        temp = temp*10 + num%10
        num /= 10
    return temp

print revDigits(1234)

Vincent Miller Moral - 2 years, 6 months ago

Log in to reply

To determine whether a given number is prime or composite. (C++ solution)

Again by counting the number of factors, making use of the property that a prime number has only 2 factors. (Sorry, @Christopher Boo )

 int n, d = 0;
 cout<<"Enter the number ";
 cin>>n;
 for( int i = 1; i<=n; i++)
 {
  if( n%i == 0)
  {
    d+=1;
  }
 }
 if( d == 2)
 {
   cout<<"The number is prime";
 }
 else
 {
   cout<<"The number is composite";
 }

Shabarish Ch - 2 years, 6 months ago

Log in to reply

thank you for sharing.

Fahima Chowdhury - 2 years, 6 months ago

Log in to reply

algorithm to calculate nth root of a number: {int n,x,y; int exponential(int x,int n); printf ("values of x & n");

scanf("%d%d",&x,&n);
y=exponential(x,n);
printf("the value of x^n:%d",y);

}
int exponential(int x,int n) { if(n==1) return x; else return (x*exponential(x,n-1)); }

Saail Narvekar - 2 years, 6 months ago

Log in to reply

For 9, you can use Euclid's algorithm to get the gcd, then use the fact that \( a * b = \gcd * \text{lcm} \) to get the lcm.

Siddhartha Srivastava - 2 years, 6 months ago

Log in to reply

@Mark Mottian There is a way to find the nth root of a number without using a function. We will use logarithms.

1
2
3
4
5
START
read value of N \\where N is the number whose rth root we have to find
read value of r
initialize variable x:= exp((1/r)log(n))
return x

@Sudeep Salgia

Raghav Vaidyanathan - 2 years, 6 months ago

Log in to reply

Problem 4 (Python 3.4.1 Solution)

Part 1 - Ascending Order

def isAscending(n):
    if sorted(str(n))== list(str(n)):
        return True
    else:
        return False

Mark Mottian - 2 years, 6 months ago

Log in to reply

Do you mean strictly increasing or equal or greater than previous? If it's the first one, your code will fail. Even if it's the latter, the built-in sorting algorithm for Python is Timsort that has a time efficiency of \(O(n\lg n)\) and memory efficiency \(O(n)\).

In my opinion, the better approach is follow the hard way. It may looks longer, but it's more efficient. As an example below, it takes only time efficiency \(O(n)\) and memory efficiency \(O(1)\).

Pseudocode

p = n[1]
for i from 2 to n.length() :
    q = n[i]
    if q < p:
        return false
        break
    else: p = q

In this way, you can either change it to strictly increasing or equal or greater than previous by using \(<\) or \(\leq\).

Christopher Boo - 2 years, 6 months ago

Log in to reply

This is very insightful! Thanks for sharing. Also, it's adaptable code because this way you can also chose whether you want to determine if a given number is strictly increasing or equal or greater than the previous.

Mark Mottian - 2 years, 6 months ago

Log in to reply

Problem 3 (Python 3.4.1 Solution)

def uniqueDigits(n):
    if sorted(set(str(n)))== sorted(list(str(n))):
        return True
    else:
        return False

Mark Mottian - 2 years, 6 months ago

Log in to reply

Problem 2 (Python 3.4.1 Solution)

import math
def isSquare(n):
    if (n**(1/2)) == int(math.sqrt(n)):
        return True
    else:
        return False

Does anybody know a way of determining if a number is a cube number, a power of 4, a power of 5 etc.?

Mark Mottian - 2 years, 6 months ago

Log in to reply

Try computing the nth root and finding its difference with its floor. If it is zero then it is a perfect nth power otherwise it ain't.

Sudeep Salgia - 2 years, 6 months ago

Log in to reply

Hi Sudeep. As always, it's always a pleasure to discuss things with you.

How do you compute the nth root of a number?

Mark Mottian - 2 years, 6 months ago

Log in to reply

@Mark Mottian Hey Mark!

In C++ the pow() function can be used like pow(a,1/n) which returns the nth root. (This is what I recall. It has been a pretty long time since I had tried this which I remember to be giving the correct output. ) I do not have any idea about Python. But if you want a platform independent algorithm without using such standard functions I would have to think about it a bit.

Sudeep Salgia - 2 years, 6 months ago

Log in to reply

@Sudeep Salgia You've actually brought up another crucial programming problem: calculating the nth root of a number

I'll add it as an extra problem (problem 11)

Mark Mottian - 2 years, 6 months ago

Log in to reply

Problem 1 (Python 3.4.1 Solution)

The logic used in this algorithm is very useful. It would be a good idea to keep it in your memory bank.

import math
def digitSum (n):
    Sum = 0
    while n > 0:
        Sum = Sum + (n % 10) #add the last digit to Sum
        n = math.floor(n/10) #remove the last digit from n
    return Sum

Similarly:

import math
def digitProduct (n):
    product = 1
    while n > 0:
        product = product * (n % 10) #multiply the last digit with product
        n = math.floor(n/10) #remove the last digit from n
    return product

Mark Mottian - 2 years, 6 months ago

Log in to reply

2.Determine whether a given number is a square number/cube number

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
START
Read N //where we need to check whether it is a perfect square/cube
initialize variable r=0 //this will hold value 1 if square only 2 if cube only and 3 if both cube and square
float k:=floor(sqrt(N))//sqrt() is the squareroot function
float l:=floor(cbrt(N))//cbrt() is the cuberoot function
k:=N-k*k
l:=N-l*l*l
If(k==0 AND l==0) then r:=3
Else If(k==0) then r:=1
Else If(l==0) then r:=2
Else r:=0
Return r
STOP

Raghav Vaidyanathan - 2 years, 6 months ago

Log in to reply

I have a doubt regarding a variant of the 4th question

How would you proceed if there were n terms(in no specificorder) and you were asked to arrange them in asc or desc order ?

Azhaghu Roopesh M - 2 years, 6 months ago

Log in to reply

We will use a sorting algorithm to sort the given number's digits in ascending/descending order.

Raghav Vaidyanathan - 2 years, 6 months ago

Log in to reply

@Raghav Vaidyanathan So would you proceed using Python or C++ ?

P.S. Have you ever check this out ? Kishlaya gave me this link today .

Azhaghu Roopesh M - 2 years, 6 months ago

Log in to reply

@Azhaghu Roopesh M @Azhaghu Roopesh M The answer is pretty easy, we do not need to use any kind of sorting algorithm. Here is the algorithm:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
START
initialize integer array dig[10], set each term to 0
Read N //N is the given number as an integer
while N>0 repeat steps 7 to 9
//start of loop
 initialize integer variable s:=N%10
    dig[s]:=dig[s]+1
    N:=N/10
//end of loop
for N=0 to N=9 repeat step 12
//start of loop
print N x[N] times
//end of loop
STOP

For ascending order.

Raghav Vaidyanathan - 2 years, 6 months ago

Log in to reply

@Azhaghu Roopesh M Yes, I did see that. It was very interesting. You seem to have a lot of collaborators! My name wouldn't figure there. I've only recently been active here and my first wiki contribution came today.

Raghav Vaidyanathan - 2 years, 6 months ago

Log in to reply

@Raghav Vaidyanathan Can you provide a link to it ?

Azhaghu Roopesh M - 2 years, 6 months ago

Log in to reply

@Azhaghu Roopesh M Here

Raghav Vaidyanathan - 2 years, 6 months ago

Log in to reply

@Raghav Vaidyanathan I'll read that up :)

Do contribute more ! Even I am planning to start on with wikis on Front End and DBMS .

Azhaghu Roopesh M - 2 years, 6 months ago

Log in to reply

@Brock Brown You're welcome!

Pi Han Goh - 2 years, 6 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...