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

– Mark Mottian · 2 years, 4 months ago

Thanks for the response! Very helpful!Log in to reply

– Aryan Gaikwad · 2 years, 3 months ago

You are welcome :)Log in to reply

– Christopher Boo · 2 years, 4 months ago

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

– Mark Mottian · 2 years, 3 months agoLog in to reply

– Aryan Gaikwad · 2 years, 3 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.Log in to reply

Ironically, most of the competitive programming problems outside brilliant.org is not "mathematical". – Christopher Boo · 2 years, 4 months ago

Log in to reply

– Azhaghu Roopesh M · 2 years, 4 months ago

Not necessarily . Have you checked out Project Euler ?Log in to reply

– Christopher Boo · 2 years, 4 months ago

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

– Azhaghu Roopesh M · 2 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 ?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

– Patrick Engelmann · 2 years, 3 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\).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.

– Shabarish Ch · 2 years, 4 months agoLog in to reply

– Christopher Boo · 2 years, 4 months agoPseudocodeLog in to reply

– Shabarish Ch · 2 years, 4 months ago

How is time efficiency determined? What is \( O(n) \) ?Log in to reply

– Christopher Boo · 2 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)\).Log in to reply

Moral: When dealing with large numbers, arithmetic operations can no longer be assumed to be constant time. – Ivan Koswara · 1 year, 12 months ago

Log in to reply

– Shabarish Ch · 2 years, 4 months ago

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

– Siddhartha Srivastava · 2 years, 4 months ago

Search "Big O Notation". I think there was a note on this here.Log in to reply

– Shabarish Ch · 2 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..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. – Raghav Vaidyanathan · 2 years, 4 months ago

Log in to reply

Log in to reply

May I question why these are algorithms everybody needs to know? – Agnishom Chattopadhyay · 1 year, 10 months ago

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 )

– Shabarish Ch · 2 years, 4 months agoLog in to reply

thank you for sharing. – Fahima Chowdhury · 2 years, 4 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");

}

int exponential(int x,int n) { if(n==1) return x; else return (x*exponential(x,n-1)); } – Saail Narvekar · 2 years, 4 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, 4 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.

@Sudeep Salgia – Raghav Vaidyanathan · 2 years, 4 months ago

Log in to reply

Problem 4(Python 3.4.1 Solution)

– Mark Mottian · 2 years, 4 months agoPart 1 - Ascending OrderLog in to reply

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\). – Christopher Boo · 2 years, 4 months agoLog in to reply

– Mark Mottian · 2 years, 3 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.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.? – Mark Mottian · 2 years, 4 months ago

Log in to reply

– Sudeep Salgia · 2 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.Log in to reply

How do you compute the nth root of a number? – Mark Mottian · 2 years, 4 months ago

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. – Sudeep Salgia · 2 years, 4 months ago

Log in to reply

I'll add it as an extra problem (problem 11) – Mark Mottian · 2 years, 4 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.

Similarly:

– Mark Mottian · 2 years, 4 months agoLog in to reply

Log in to reply

4th questionHow would you proceed if there were

nterms(in no specificorder) and you were asked to arrange them in asc or desc order ? – Azhaghu Roopesh M · 2 years, 4 months agoLog in to reply

– Raghav Vaidyanathan · 2 years, 4 months ago

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 . – Azhaghu Roopesh M · 2 years, 4 months ago

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. – Raghav Vaidyanathan · 2 years, 4 months ago

Log in to reply

– Raghav Vaidyanathan · 2 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.Log in to reply

– Azhaghu Roopesh M · 2 years, 4 months ago

Can you provide a link to it ?Log in to reply

Here – Raghav Vaidyanathan · 2 years, 4 months ago

Log in to reply

Do contribute more ! Even I am planning to start on with wikis on Front End and DBMS . – Azhaghu Roopesh M · 2 years, 4 months ago

Log in to reply

@Brock Brown You're welcome! – Pi Han Goh · 2 years, 4 months ago

Log in to reply