Posts

Modulus of a Big number

 How to Evaluate Modulus of  very large numbers ? We know the modular addition property which is: IF N = a + b, then N % n = ( a + b ) % n . Which can be written as :   N % n = ( ( a % n ) + ( b % n) ) % n Lets say we want to calculate 123456 % 7 . Let's consider  : For a number 123 % 7 it can be evaluated as  ( 120 + 3 ) %7 Now 12 = 12 + 12 + 12 + ............ + 12 ; adding 12, 10 times will give us 120. So Applying the modular addition formula we get :  ( ( 12 +12+12+.........+12)  + 3 ) ) % 7 (  ( 12 % 7 ) + ( 12  % 7 ) + ........ + ( 12 % 7 ) + ( 3 % 7 ) ) % 7 ( ( 12 % 7) * 10  + ( 3 % 10 ) ) % 7 Now the modulus of the number 123456 can be represented like this: 1 % 7 -> ( 0 *10 + 1 ) % 7 12 % 7 -> ( 10+2 ) % 7= ( 1 % 7 )*10 + ( 2 % 7) ) % 7   123 -> ( 120+3 ) % 7 = ( (12 % 7 ) * 10 + ( 3 % 7 ) ) % 7 1234 ->  ( 1230+4 ) % 7 = ( (123 % 7 ) * 10 + ( 4 % 7 ) ) % 7 12345 ->  ( 12340 + 5 ) % 7 = ( (1234 ...
Post a Comment
Read more

CSES Problem Set Solution (Distinct Number)

Image
 Solution In C++ Distinct Numbers problem is from the category of Sorting and Searching . Its the first problem of this section. The problem statement can be read here . This is a very basic problem which requires us to count the number of distinct integer values. Time limit is one second and constrain for every i'th integer value is 10^9. So for the array where we are going to store the integers we'll take the type as long long int. We will take a counter to count distinct values. Which cannot be greater than n (number of integer values). We can solve the problem in following approach: We will sort the array first then iterate through the array having a variable temp (which will temporarily store the current value which we will use while iterating if its the same value or not. If not, temp will be updated and count will increment. As we sorted the array same values will appear once in a substring.  this can be visualized below: This problem can also be solved using a set. A s...
1 comment
Read more