10 Basic Algorithms Every Programmer Should Know

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

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

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

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

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.

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

@Brock Brown You're welcome!

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

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

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

Problem 3 (Python 3.4.1 Solution)

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

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

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.

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

thank you for sharing.

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

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)

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