loading...

Daily HackerRank Challenge - Day 6

wingkwong profile image Wing-Kam ・2 min read

Daily HackerRank Challenge (30 Part Series)

1) Daily HackerRank Challenge - Day 0 2) Daily HackerRank Challenge - Day 1 3 ... 28 3) Daily HackerRank Challenge - Day 2 4) Daily HackerRank Challenge - Day 3 5) Daily HackerRank Challenge - Day 4 6) Daily HackerRank Challenge - Day 5 7) Daily HackerRank Challenge - Day 6 8) Daily HackerRank Challenge - Day 7 9) Daily HackerRank Challenge - Day 8 10) Daily HackerRank Challenge - Day 9 11) Daily HackerRank Challenge - Day 10 12) Daily HackerRank Challenge - Day 11 13) Daily HackerRank Challenge - Day 12 14) Daily HackerRank Challenge - Day 13 15) Daily HackerRank Challenge - Day 14 16) Daily HackerRank Challenge - Day 15 17) Daily HackerRank Challenge - Day 16 18) Daily HackerRank Challenge - Day 17 19) Daily HackerRank Challenge - Day 19 20) Daily HackerRank Challenge - Day 20 21) Daily HackerRank Challenge - Day 21 22) Daily HackerRank Challenge - Day 22 23) Daily HackerRank Challenge - Day 23 24) Daily HackerRank Challenge - Day 24 25) Daily HackerRank Challenge - Day 25 26) Daily HackerRank Challenge - Day 26 27) Daily HackerRank Challenge - Day 27 28) Daily HackerRank Challenge - Day 28 29) Daily HackerRank Challenge - Day 29 30) Daily HackerRank Challenge - Day 30

About

This is a series of Daily HackerRank Challenge. Each day I show the some solutions written in C++.


#001: Multiples of 3 and 5

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3,5,6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below N.

Sample Input

2
10
100

Sample Output

23
2318

To sum from 1 to i, it is

s=1+2+3...+(i-1)+i

if you reverse the order

s=1+2+3...+(i-1)+i
s=i+(i-1)+(i-2)+...+2+1

summing each value, we got

2s=(i+1)+(i+1)+...(i+1)+(i+1)

and there are i (i+1) in above formula

2s=i(i+1)

at the end, we got

s=i(i+1)/2

We can use s=i(i+1)/2 to caculate the sum from 1 to i. However, the question just needs us to calculate the sum of the multiples of 3 or 5.

Take 3 as an example

s=3+6+9+...+3i
s=3(1+2+3+...+i)

We know that 1+2+3+...+i can be calculated using s=i(i+1)/2. Therefore, we now know

s=3(1+2+3+...+i)
s=3(i(i+1)/2)

where

3i <= n
i <= n/3 

it becomes

s=n((n/k)((n/k)+1)/2)

The question states that it only requires the multiples of K below N, that means it does not include N, hence we should substract N from 1.

However, if we sum up multiples of 3 and multiples of 5, we can get duplicate values, i.e. 15 in below example

multiples of 3: 3,6,9,15,18...
multiples of 5: 5,10,15,20,...

Hence, we need to subtract the series of their least common multiple (LCM) which is 15. The final answer is

S(3) + S(5) - S(15)

Final Solution:

ll t,i,x;

ll s(ll n,ll k){
    x = n/k;
    return (k*(x*(x+1)))/2;
}

int main()  
{ 
    FAST_INP;

    cin >> t;
    TC(t){
        cin >> i;
        cout << s(i-1,3)+s(i-1,5)-s(i-1,15) << "\n";
    }
    return 0; 
}

Complete Code

Check out the complete code via below link

Daily HackerRank Challenge (30 Part Series)

1) Daily HackerRank Challenge - Day 0 2) Daily HackerRank Challenge - Day 1 3 ... 28 3) Daily HackerRank Challenge - Day 2 4) Daily HackerRank Challenge - Day 3 5) Daily HackerRank Challenge - Day 4 6) Daily HackerRank Challenge - Day 5 7) Daily HackerRank Challenge - Day 6 8) Daily HackerRank Challenge - Day 7 9) Daily HackerRank Challenge - Day 8 10) Daily HackerRank Challenge - Day 9 11) Daily HackerRank Challenge - Day 10 12) Daily HackerRank Challenge - Day 11 13) Daily HackerRank Challenge - Day 12 14) Daily HackerRank Challenge - Day 13 15) Daily HackerRank Challenge - Day 14 16) Daily HackerRank Challenge - Day 15 17) Daily HackerRank Challenge - Day 16 18) Daily HackerRank Challenge - Day 17 19) Daily HackerRank Challenge - Day 19 20) Daily HackerRank Challenge - Day 20 21) Daily HackerRank Challenge - Day 21 22) Daily HackerRank Challenge - Day 22 23) Daily HackerRank Challenge - Day 23 24) Daily HackerRank Challenge - Day 24 25) Daily HackerRank Challenge - Day 25 26) Daily HackerRank Challenge - Day 26 27) Daily HackerRank Challenge - Day 27 28) Daily HackerRank Challenge - Day 28 29) Daily HackerRank Challenge - Day 29 30) Daily HackerRank Challenge - Day 30

Posted on by:

wingkwong profile

Wing-Kam

@wingkwong

Consultant by day. Developer by night. AWS certified. Exploring #CloudNative currently.

Discussion

markdown guide