# 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
6 years, 4 months ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$ ... $$ or $ ... $ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

Sort by:

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 set = new HashSet(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 list = new ArrayList(); 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 list = new ArrayList(); 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); } 

- 6 years, 4 months ago

Thanks for the response! Very helpful!

- 6 years, 4 months ago

You are welcome :)

- 6 years, 4 months ago

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

- 6 years, 4 months ago

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


- 6 years, 4 months ago

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.

- 6 years, 4 months ago

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

- 6 years, 4 months ago

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

- 6 years, 3 months ago

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

- 6 years, 4 months ago

Not necessarily . Have you checked out Project Euler ?

- 6 years, 4 months ago

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

- 6 years, 4 months ago

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 ?

- 6 years, 4 months ago

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 

- 6 years, 4 months ago

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.

- 6 years, 4 months ago

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";
}


- 6 years, 4 months ago

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


- 6 years, 4 months ago

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

- 6 years, 4 months ago

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

- 6 years, 4 months ago

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

- 6 years, 4 months ago

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)$.

- 6 years, 4 months ago

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.

- 6 years ago

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

- 6 years, 4 months ago

@Brock Brown You're welcome!

- 6 years, 4 months ago

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 

- 6 years, 4 months ago

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 ?

- 6 years, 4 months ago

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

- 6 years, 4 months ago

So would you proceed using Python or C++ ?

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

- 6 years, 4 months ago

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.

- 6 years, 4 months ago

Can you provide a link to it ?

- 6 years, 4 months ago

Here

- 6 years, 4 months ago

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

- 6 years, 4 months ago

@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.

- 6 years, 4 months ago

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


- 6 years, 4 months ago

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.?

- 6 years, 4 months ago

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.

- 6 years, 4 months ago

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

How do you compute the nth root of a number?

- 6 years, 4 months ago

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.

- 6 years, 4 months ago

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)

- 6 years, 4 months ago

Problem 3 (Python 3.4.1 Solution)

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


- 6 years, 4 months ago

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


- 6 years, 4 months ago

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$.

- 6 years, 4 months ago

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.

- 6 years, 4 months ago

@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 

- 6 years, 4 months ago

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.

- 6 years, 4 months ago

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)); }

- 6 years, 4 months ago

thank you for sharing.

- 6 years, 4 months ago

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";
}


- 6 years, 4 months ago

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) 

- 6 years, 4 months ago

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

- 5 years, 10 months ago