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.