Basics
Number theory involves various types of integers like prime numbers, composite numbers, and the relation between them. Base numbers and arithmetics numbers are also the topics involved in number theory. Following are some fundamental number theory problems every programmer should be well aware of.
Prime Numbers
An elementary math concept, those numbers which have only 2 factors, the number itself and 1 are called Prime Numbers. Let's discuss more the same!
Segmented Sieve
By Ayush Prakash
● Published At Feb 2022
In this problem, we are going to learn a very important concept in number theory, “Segmented Sieve”. We are also going to analyse the space and time complexity of the approach. ... Keep reading ..
Sieve of Eratosthenes with Linear time complexity
By Sneha Mallik
● Published At Oct 2021
This blog covers the basic concepts of the sieve of Eratosthenes done within linear time complexity.... Keep reading ..
Integer Factorization
By Pranav Gautam
● Published At Oct 2021
Learn different methods to perform integer factorization of prime and composite numbers. ... Keep reading ..
Primality Tests
By Husen Kagdi
● Published At Oct 2021
In this blog, we will discuss naive tests and the Fermat tests to check whether a given number is prime or not.... Keep reading ..
Kth Smallest Prime Number in range L to R for Q queries
By Saksham Gupta
● Published At Jan 2022
This blog will discuss how we can solve the problem named ‘Kth smallest Prime Number in range L to R for Q queries’.... Keep reading ..
Find Prime Numbers in a 2D Array (Matrix)
By Saksham Gupta
● Published At Jan 2022
This blog will discuss how we can solve the problem named ‘Find Prime numbers in a 2D Array (Matrix)’. ... Keep reading ..
Minimum steps to reduce N to a prime number by subtracting with its highest divisor
By Sandeep kamila
● Published At Jan 2022
This article discusses the approach to finding the minimum steps required to reduce N to a prime number by subtracting with its highest divisor with its implementation in C++.... Keep reading ..
Minimize Swaps Required to Make All Prime-indexed Elements as Prime
By Sujal Modanwal
● Published At Jan 2022
The task is to make all prime-indexed elements of the array prime with minimum swaps.... Keep reading ..
Find Any Prime Number P contains given Number N.
By Vaibhav Agarwal
● Published At Jan 2022
In this article, we will discuss the problem of finding the Prime Number P contains given Number N in it.... Keep reading ..
Make two numbers equal by multiplying with their prime factors the minimum number of times
By Ayush Tiwari
● Published At Jan 2022
This blog finds the minimum number of operations needed to make two numbers equal by multiplying with their prime factors... Keep reading ..
Segregate Prime and Non-Prime Numbers In An Array
By Harsh Goyal
● Published At Jan 2022
This article will discuss segregating the prime and the non-prime numbers in an array and various ways to solve this problem. ... Keep reading ..
Program To Find The Nth Composite Number
By Rhythm Jain
● Published At Feb 2022
Combinatorics
Combinatorics, the field of mathematics concerned with problems of selection, arrangement, and operation within a finite or discrete system. In this category, we will explore more about combinatorics.
Count Number of Valid Parenthesis
● Published At Oct 2021
This article discusses the problem “ count number of valid parenthesis, “where we have to calculate the total number of valid parentheses for a given integer.... Keep reading ..
Catalan Numbers
By dhruv sharma
● Published At Dec 2021
Catalan numbers are a unique number sequence found helpful in various combinatorial and counting problems. We will also talk about its generation using different approaches and their applications. ... Keep reading ..
Number of ways you can always stay either above or below the main diagonal
By Nishant Rana
● Published At Jan 2022
This blog will cover how to find the number of ways you can always stay either above or below the main diagonal and discuss their Time and Space complexity. ... Keep reading ..
Count all binary strings having length N and contain at least X 0's and Y 1's.
By Vaibhav Agarwal
● Published At Feb 2022
This article will discuss the problem of finding the count of all binary strings having length N that contains at least X 0’s and Y 1’s.... Keep reading ..
Count of numbers of length N having odd numbers at even indices and prime numbers at odd indices
By Sandeep kamila
● Published At Jan 2022
This article discusses the approach to count the numbers of length N having odd numbers at even indices and prime numbers at odd indices and its implementation in C++.... Keep reading ..
Minimum adjacent swaps of the digits required to make N divisible by K
By Sandeep kamila
● Published At Jan 2022
This article discusses the approach to finding the minimum adjacent swaps of the digits required to make N divisible by K with its C++ code.... Keep reading ..
Maximum product of integers formed by splitting digits of N into two parts in any permutation
By Sandeep kamila
● Published At Jan 2022
This article discusses the approach to maximize the product of integers formed by splitting the digits of N into two parts in any permutation with its C++ code.... Keep reading ..
Count of all the possible combinations of K numbers that sum up to N
By Sandeep kamila
● Published At Jan 2022
This article discusses the different approaches to counting all possible combinations of K numbers that sum up to N.... Keep reading ..
E. Counting Arrays
By Manan Singhal
● Published At May 2022
In this article, we will solve one of the popular problems, E. counting arrays... Keep reading ..
Binomial Coefficients
By Harsh Goyal
● Published At Oct 2021
This article will introduce Binomial Coefficients and provide approaches to use them in different data structure problems.... Keep reading ..
Nice Permutations
By Riya
● Published At Mar 2022
This article will discuss the problem “Nice Permutations”, solution approach to the problem, its C++ implementation, and its time and space complexities.... Keep reading ..
Modular Arithmetic
Modulo Fermat's Theorem
By Saksham Gupta
● Published At Mar 2022
This blog will discuss a famous number theory question - Modulo Fermat's Theorem. ... Keep reading ..
Stickman Tree
By Teesha Goyal
● Published At May 2022
Ninja and Chains
By Saksham Gupta
● Published At Mar 2022
This blog will discuss how we can solve a problem - Ninja and Chains. ... Keep reading ..
Common Problems
The basic topics that come under Number Theory are Prime Numbers, GCD, Extended Euclid Algorithm, Modular Arithmetic, etc. Questions from these topics are also asked in the interviews of Top Product-Based Companies. Hence, one needs to practice questions from these topics to excel interviews.
Find the Array which when sorted forms an AP and has Least Maximum
By Riya
● Published At Feb 2022
This article will discuss the problem "Find the array which when sorted forms an AP and has least maximum," the solution approach to this problem, its C++ implementation, and its time and space complexity.... Keep reading ..
Count of Arrangements of RGB balls with No Duplicates in a Set
By Sujal Modanwal
● Published At Dec 2021
Balls of three colours are given Red, Green, and Blue colours. The task is to calculate the minimum required sets to place all the RGB balls.... Keep reading ..
Minimum Operations Necessary to Reduce N to 0 by Substituting N with N/M or Increasing M by 1
By Sujal Modanwal
● Published At Jan 2022
Minimum number of operations required to reduce N to 0 by substituting either N with N/M or increasing M by 1. ... Keep reading ..
Smallest divisor of N closest to X
By Sandeep kamila
● Published At Jan 2022
This article discusses the different approaches to find the Smallest divisor of N closest to X with a complete explanation in C++.... Keep reading ..
Check if a Number can be Expressed as Product of a Prime and a Composite Number
By Aman kumar Chourasiya
● Published At Jan 2022
In this blog we will discuss a coding challenge based on factorization techniques. We will see how to implement Sieve of Eratosthenes to identify prime numbers upto a given limit.... Keep reading ..
Finding Power of Factorial Divisor
● Published At Oct 2021
This article covers finding the power of factorial divisors and discusses its implementation in C++. ... Keep reading ..
Count of numbers from the range [L, R] whose sum of digits is Y
By Husen Kagdi
● Published At Feb 2022
In this blog, we will discuss a range query problem named count of numbers from the range [L, R] whose sum of digits is Y. ... Keep reading ..
Count Prime in Ranges
By Husen Kagdi
● Published At Oct 2021
This blog discusses a famous interview problem, count prime in ranges. Given a range L and R, we need to find the number of primes between L and R inclusive.... Keep reading ..
Minimize the count of integers to be added in Array to make each adjacent pair co-prime
By Urwashi Priya
● Published At Jan 2022
This article will brief you on the problem to minimize the count of integers to be added in an array to make each adjacent pair co-prime.... Keep reading ..
Find the longest subarray with Prime sum in given Array
By Yukti Kumari
● Published At Jan 2022
This article explains the problem to find the longest subarray with a prime sum in a given array. ... Keep reading ..
Count array elements whose count of divisors is a prime number
By Urwashi Priya
● Published At Jan 2022
This article will brief you on the problem to Count array elements whose count of divisors is a prime number. ... Keep reading ..
Prime Numbers from 1 to N that can be Represented as a Sum of Two Prime Numbers
By GAZAL ARORA
● Published At Mar 2022
Prime numbers have only two factors, 1 and themselves. In this article, we will write an algorithm to count prime numbers from 1 to N that can be written as a sum of two prime numbers.... Keep reading ..
Find Kth Number, Which can be Written as the Sum of Powers of ‘N’
By Ujjawal Gupta
● Published At Jan 2022
In this blog, we will learn to solve a problem based on bit manipulation.... Keep reading ..