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:

- Determine the
**sum of the digits/product of the digits**of a particular number - Determine whether a given number is a
**square number/cube number** - Determine whether a given number has
**unique digits** - Determine whether the digits of a number are in
**ascending/descending order** - Determine whether a given number is
**prime or composite** - Determine the
**prime factorisation**for a given number - Determine the
**number of factors**a particular number has - Determine the
**nth Fibonacci number** - Determine the
**LCM and GCD**of two or more given numbers **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**

## Comments

Sort by:

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

Product of digits (number is stored as String) -

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

Determine whether a given number is a cube number -

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

4) Check if digits are in ascending order -

Check if digits are in descending order -

5) Prime / Composite test -

6) Prime Factorization -

7) Number of factors -

8) Nth Fibonacci Number -

9) GCD -

LCM -

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

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

Log in to reply

Thanks for the response! Very helpful!

Log in to reply

You are welcome :)

Log in to reply

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

Log in to reply

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

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.

Log in to reply

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

Log in to reply

Not necessarily . Have you checked out Project Euler ?

Log in to reply

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

Log in to reply

Log in to reply

To determine the sum of digits of a particular number.

Start

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

Input \( n \),

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

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

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

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

Print \( s \)

Stop

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

Log in to reply

To find whether the number is a

perfect squarebycounting the number of factors. (C++ solution)It makes use of the property that a perfect square has odd number of factors.

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.

PseudocodeLog in to reply

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

Log in to reply

Log in to reply

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

Log in to reply

Log in to reply

Log in to reply

Log in to reply

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

Log in to reply

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

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 )

Log in to reply

thank you for sharing.

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

}

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

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.

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.

@Sudeep Salgia

Log in to reply

Problem 4(Python 3.4.1 Solution)Part 1 - Ascending OrderLog in to reply

Do you mean

strictly increasingorequal 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)\).

PseudocodeIn this way, you can either change it to

strictly increasingorequal or greater than previousby using \(<\) or \(\leq\).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.

Log in to reply

Problem 3(Python 3.4.1 Solution)Log in to reply

Problem 2(Python 3.4.1 Solution)Does anybody know a way of determining if a number is a cube number, a power of 4, a power of 5 etc.?

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.

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?

Log in to reply

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.

Log in to reply

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

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.

Similarly:

Log in to reply

Log in to reply

I have a doubt regarding a variant of the

4th questionHow would you proceed if there were

nterms(in no specificorder) and you were asked to arrange them in asc or desc order ?Log in to reply

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

Log in to reply

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

Log in to reply

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

For ascending order.

Log in to reply

Log in to reply

Log in to reply

Here

Log in to reply

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

Log in to reply

@Brock Brown You're welcome!

Log in to reply