Given a number N in decimal base, the task is to find the sum of digits of the number in any base B.
Examples:
Input: N = 100, B = 8
Output: 9
Explanation:
(100)8 = 144
Sum(144) = 1 + 4 + 4 = 9Input: N = 50, B = 2
Output: 3
Explanation:
(50)2 = 110010
Sum(110010) = 1 + 1 + 0 + 0 + 1 + 0 = 3
Approach: Find unit digit by performing modulo operation on number N by base B and updating the number again by N = N / B and update sum by adding the unit digit at each step.
Below is the implementation of above approach
C++
// C++ Implementation to Compute Sum of// Digits of Number N in Base B#include <iostream>using namespace std;// Function to compute sum of// Digits of Number N in base Bint sumOfDigit(int n, int b){ // Initialize sum with 0 int unitDigit, sum = 0; while (n > 0) { // Compute unit digit of the number unitDigit = n % b; // Add unit digit in sum sum += unitDigit; // Update value of Number n = n / b; } return sum;}// Driver functionint main(){ int n = 50; int b = 2; cout << sumOfDigit(n, b); return 0;} |
Java
// Java Implementation to Compute Sum of// Digits of Number N in Base Bimport java.io.*;public class GFG{// Function to compute sum of// Digits of Number N in base Bstatic int sumOfDigit(int n, int b){ // Initialize sum with 0 int unitDigit, sum = 0; while (n > 0) { // Compute unit digit of the number unitDigit = n % b; // Add unit digit in sum sum += unitDigit; // Update value of Number n = n / b; } return sum;}// Driver codepublic static void main(String[] args){ int n = 50; int b = 2; System.out.print(sumOfDigit(n, b));}}// This code is contributed by PrinciRaj1992 |
Python3
# Python3 Implementation to Compute Sum of# Digits of Number N in Base B# Function to compute sum of# Digits of Number N in base Bdef sumOfDigit(n, b): # Initialize sum with 0 unitDigit = 0 sum = 0 while (n > 0): # Compute unit digit of the number unitDigit = n % b # Add unit digit in sum sum += unitDigit # Update value of Number n = n // b return sum# Driver coden = 50b = 2print(sumOfDigit(n, b))# This code is contributed by ApurvaRaj |
C#
// C# Implementation to Compute Sum of // Digits of Number N in Base B using System;class GFG { // Function to compute sum of // Digits of Number N in base B static int sumOfDigit(int n, int b) { // Initialize sum with 0 int unitDigit, sum = 0; while (n > 0) { // Compute unit digit of the number unitDigit = n % b; // Add unit digit in sum sum += unitDigit; // Update value of Number n = n / b; } return sum; } // Driver code public static void Main(String[] args) { int n = 50; int b = 2; Console.Write(sumOfDigit(n, b)); } }// This code is contributed by PrinciRaj1992 |
Javascript
<script>// Javascript Implementation to Compute Sum of // Digits of Number N in Base B // Function to compute sum of // Digits of Number N in base B function sumOfDigit(n, b) { // Initialize sum with 0 var unitDigit, sum = 0; while (n > 0) { // Compute unit digit of the number unitDigit = n % b; // Add unit digit in sum sum += unitDigit; // Update value of Number n = parseInt(n / b); } return sum; } // Driver function var n = 50; var b = 2; document.write(sumOfDigit(n, b)); // This code is contributed by rutvik_56.</script> |
3
Time Complexity: O(logbN), where N is the given number
Auxiliary Space: O(1)
Approach 2: Using Recursion:
In this approach, we define a function sumOfDigit that takes two arguments – the number n and the base b. The function first checks for the base case, which is when the number becomes 0, and returns 0. Otherwise, the function computes the sum of the unit digit (i.e., the remainder when n is divided by b) and the sum of digits of the quotient (i.e., n divided by b) recursively.
This approach is also efficient and readable, and can handle large numbers without the risk of overflow.
Here is the code of above approach:
C++
#include <iostream>using namespace std;// Function to compute sum of digits of number n in base bint sumOfDigit(int n, int b) { // Base case if (n == 0) { return 0; } // Recursive step return (n % b) + sumOfDigit(n / b, b);}// Driver functionint main() { int n = 50; int b = 2; cout << sumOfDigit(n, b) << endl; return 0;} |
Java
/*package whatever //do not write package name here */public class SumOfDigits { // Function to compute sum of digits of number n in base b public static int sumOfDigit(int n, int b) { // Base case if (n == 0) { return 0; } // Recursive step return (n % b) + sumOfDigit(n / b, b); } // Driver function public static void main(String[] args) { int n = 50; int b = 2; System.out.println(sumOfDigit(n, b)); }} |
Python3
def sum_of_digit(n, b): # Base case if n == 0: return 0 # Recursive step return (n % b) + sum_of_digit(n // b, b)# Driver functionif __name__ == '__main__': n = 50 b = 2 print(sum_of_digit(n, b)) |
C#
using System;public class SumOfDigits{ // Function to compute sum of digits of number n in base b public static int SumOfDigit(int n, int b) { // Base case if (n == 0) { return 0; } // Recursive step return (n % b) + SumOfDigit(n / b, b); } // Driver function public static void Main(string[] args) { int n = 50; int b = 2; System.Console.WriteLine(SumOfDigit(n, b)); }} |
Javascript
// JavaScript program for the above approach. function sum_of_digit(n, b) {// Base caseif (n == 0) {return 0;}// Recursive stepreturn (n % b) + sum_of_digit(Math.floor(n / b), b);}// Driver functionlet n = 50;let b = 2;console.log(sum_of_digit(n, b));// Contributed by adityasharmadev01 |
3
Time Complexity: O(logbN), where N is the given number
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
