Sum of last digit of all integers from 1 to N divisible by M

0 0 5 minutes read

Given two integer N and N. The task is to compute the sum of last digit of all integers from 1 to N that is divisible by M.

Examples:

Input: N = 12, M = 1
Output: 48
Number divisible by M = 1 from 1 to 12 is :
{1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 0 + 1 + 2} = 48

Input: N = 100, M = 3
Output: 153

Approach: The problem is based on simple observation.
Let k = floor(N/M) be the number of integers from 1 to N divisible by M.
Since the last digits are needed to be added in the original sum. So, the last digit can be in the range of 0 to 9 and the cycle can be formed by observing the array pattern.
So for each cycle, sum = sum of first 10 last digits, after this, we can divide k by 10 and add the last digit of remaining numbers from starting.
So, Sum = (no. of the cycle * sum of the last digit of first 10 integers divisible by M) + (sum of the last digit of k%10 integers divisible by M).

Below is the implementation of the above approach:

C++

// C++ implementation
// of the approach
#include<iostream>
using namespace std;
 
#define long long long
 
// Function to return the 
// required sum
long sumOfLastDig(long n, long m) {
 
    long sum = 0, k;
 
    // Number of element between
    // 1 to n divisible by m
    k = n/m;
 
    // Array to store the last digit
    // of elements in a cycle
    long arr[10];
 
    // Storing and adding last
    // digit of cycle
    for (int i = 0; i < 10; i++) {
        arr[i] = m*(i+1) % 10;
        sum += arr[i];
    }
 
    // Number of elements
    // present in last cycle
    long rem = k % 10;
 
    // Sum of k/10 cycle
    long ans = (k/10)*sum;
 
    // Adding value of digits
    // of last cycle to the answer
    for (int i = 0; i < rem; i++) {
        ans += arr[i];
    }
 
    return ans;
}
 
// Driver Code
int main() {
 
    // input n and m
    long n = 100, m = 3;
 
    cout<<sumOfLastDig(n,m);
    return 0;
}

Java

// Java implementation of the approach
import java.io.*;
 
class GFG 
{
     
// Function to return the required sum
static long sumOfLastDig(long n, long m) 
{
    long sum = 0, k;
 
    // Number of element between
    // 1 to n divisible by m
    k = n / m;
 
    // Array to store the last digit
    // of elements in a cycle
    long []arr = new long[10];
 
    // Storing and adding last
    // digit of cycle
    for (int i = 0; i < 10; i++) 
    {
        arr[i] = m * (i + 1) % 10;
        sum += arr[i];
    }
 
    // Number of elements
    // present in last cycle
    long rem = k % 10;
 
    // Sum of k/10 cycle
    long ans = (k / 10) * sum;
 
    // Adding value of digits
    // of last cycle to the answer
    for (int i = 0; i < rem; i++) 
    {
        ans += arr[i];
    }
    return ans;
}
 
// Driver Code
public static void main (String[] args)
{
 
    // input n and m
    long n = 100, m = 3;
     
    System.out.println(sumOfLastDig(n, m));
}
}
 
// This code is contributed by jit_t

Python3

# Python3 implementation of the approach 
 
# Function to return the 
# required sum 
def sumOfLastDig(n, m) : 
 
    sum = 0; 
 
    # Number of element between 
    # 1 to n divisible by m 
    k = n // m;
     
    # Array to store the last digit
    # of elements in a cycle
    arr = [0] * 10; 
 
    # Storing and adding last 
    # digit of cycle 
    for i in range(10) :
        arr[i] = m * (i + 1) % 10; 
        sum += arr[i]; 
 
    # Number of elements 
    # present in last cycle 
    rem = k % 10; 
 
    # Sum of k/10 cycle 
    ans = (k // 10) * sum; 
 
    # Adding value of digits 
    # of last cycle to the answer 
    for i in range(rem) :
        ans += arr[i]; 
 
    return ans; 
 
# Driver Code 
if __name__ == "__main__" : 
 
    # input n and m 
    n = 100; m = 3; 
 
    print(sumOfLastDig(n, m)); 
 
# This code is contributed by AnkitRai01

C#

// C# implementation of the approach
using System;
 
class GFG
{
         
// Function to return the required sum
static long sumOfLastDig(long n, long m) 
{
    long sum = 0, k;
 
    // Number of element between
    // 1 to n divisible by m
    k = n / m;
 
    // Array to store the last digit
    // of elements in a cycle
    long []arr = new long[10];
 
    // Storing and adding last
    // digit of cycle
    for (int i = 0; i < 10; i++) 
    {
        arr[i] = m * (i + 1) % 10;
        sum += arr[i];
    }
 
    // Number of elements
    // present in last cycle
    long rem = k % 10;
 
    // Sum of k/10 cycle
    long ans = (k / 10) * sum;
 
    // Adding value of digits
    // of last cycle to the answer
    for (int i = 0; i < rem; i++) 
    {
        ans += arr[i];
    }
    return ans;
}
 
// Driver Code
static public void Main ()
{
     
    // input n and m
    long n = 100, m = 3;
     
    Console.Write(sumOfLastDig(n, m));
}
}
 
// This code is contributed by ajit.

Javascript

<script>
 
// Javascript implementation
// of the approach
 
// Function to return the 
// required sum
function sumOfLastDig(n, m)
{
 
    let sum = 0, k;
 
    // Number of element between
    // 1 to n divisible by m
    k = parseInt(n/m);
 
    // Array to store the last digit
    // of elements in a cycle
    let arr = new Array(10);
 
    // Storing and adding last
    // digit of cycle
    for (let i = 0; i < 10; i++) {
        arr[i] = m*(i+1) % 10;
        sum += arr[i];
    }
 
    // Number of elements
    // present in last cycle
    let rem = k % 10;
 
    // Sum of k/10 cycle
    let ans = parseInt(k/10)*sum;
 
    // Adding value of digits
    // of last cycle to the answer
    for (let i = 0; i < rem; i++) 
    {
        ans += arr[i];
    }
 
    return ans;
}
 
// Driver Code
 
    // input n and m
    let n = 100, m = 3;
 
    document.write(sumOfLastDig(n,m));
 
</script>

Output:

Time Complexity: O(10)

Auxiliary Space: O(10)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!