Find sum of all n digits which come in power of 2 of given number n

By | October 30, 2023
0 Comment

Problem: Given an integer ‘n’, find sum of all n digits which come in power of 2 of given number n.

Examples:

Input: p = 9
Output: 8
Explanation : 2^9 = 512 Digit sum : 5 + 1 + 2 = 8

Input: p = 48
Output: 73
Explanation :  2^48 = 281474976710656 Digit sum : 73

RECOMMENDED: Find the Minimum element in a Sorted and Rotated Array

The idea is simple,

  • We calculate the power of 2 and store the value in variable.
  • Then calculate digit sum.

Implementation in Java:

// Java program to find the power digit sum
import java.io.*;
import java.util.*;
import java.math.*;

public class Cpp {
    // return the (2^p) digit sum
    static int power_digit_sum(int p) {
        int sum = 0;

        BigInteger a1, a2;
        a1 = new BigInteger("2");

        // calculate power of 2 using pow function
        a2 = a1.pow(p);

        // convert the BigInteger into string to calculate digit sum
        String number = a2.toString();

        // calculate the power digit sum
        for (int i = 0; i < number.length(); i++)
            sum += (int)(number.charAt(i) - '0');

        return sum;
    }

    // Driver method
    public static void main(String[] args) {
        int p = 48;
        System.out.println("Power digit sum: " + power_digit_sum(p));
    }
}

Output:

Power digit sum: 73

Above Power function can be optimized to O(logn) by calculating power(x, y/2) only once and storing it.

// Function to calculate x = 2 raised to the power y in O(log n)
static BigInteger power(int y) {
    BigInteger temp, x;
    x = new BigInteger("2");

    if (y == 0)
        return new BigInteger("1");

    temp = power(y / 2);

    if (y % 2 == 0)
        return temp.multiply(temp);
    else {
        temp = temp.multiply(temp);
        return temp.multiply(x);
    }
}

Time Complexity: O(logn)
Space Complexity: O(1)

Please write comments below if you find anything incorrect, or you want to share more information about the topic discussed above. A gentle request to share this topic on your social media profile.

Related Posts