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} = 48Input: 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 sumlong 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 Codeint main() { // input n and m long n = 100, m = 3; cout<<sumOfLastDig(n,m); return 0;} |
Java
// Java implementation of the approachimport java.io.*;class GFG { // Function to return the required sumstatic 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 Codepublic 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 approachusing System;class GFG{ // Function to return the required sumstatic 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 Codestatic 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 sumfunction 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:
153
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
