Wednesday, 27 Oct 2021

# Sum of quotients of division of N by powers of K not exceeding N

Sum of quotients of division of N by powers of K not exceeding N
Given two positive integers N and K, the task is to find the sum of the quotients of division of N by powers of K which are less than or equal to N.
Examples:

Input: N = 10, K = 2Output: 18Explanation:Dividing 10 by 1 (= 20). Quotient = 10. Therefore, sum = 10. Dividing 10 by 2 (= 21). Quotient = 5. Therefore, sum = 15. Divide 10 by 4 (= 22). Quotient = 2. Therefore, sum = 17. Divide 10 by 8 (= 23). Quotient = 1. Therefore, sum = 18.
Input: N = 5, K=2Output: 8Explanation:Dividing 5 by 1 (= 20). Quotient = 5. Therefore, sum = 5. Divide 5 by 2 (= 21). Quotient = 2. Therefore, sum = 7. Divide 5 by 4 (= 22). Quotient = 1. Therefore, sum = 8.

Approach: The idea is to iterate a loop while the current power of K is less than or equal to N and keep adding the quotient to the sum in each iteration.Follow the steps below to solve the problem:Initialize a variable, say sum, to store the required sum.
Initialize a variable, say i = 1 (= K0) to store the powers of K.
Iterate until the value of i ≤ N, and perform the following operations:
Store the quotient obtained on dividing N by i in a variable, say X.
Add the value of X to ans and multiply i by K to obtain the next power of K.

Print the value of the sum as the result.
Below is the implementation of the above approach:

C++

#include
using namespace std;

int findSum(int N, int K)
{

int ans = 0;
int i = 1;

while (i