Given two positive integers N and K, the task is to find the sum of the quotients of the division of N by powers of K which are less than or equal to N.
Examples:
Input: N = 10, K = 2
Output: 18
Explanation:
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=2
Output: 8
Explanation:
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++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate sum of// quotients obtained by dividing// N by powers of K <= Nint findSum(int N, int K){ // Store the required sum int ans = 0; int i = 1; // Iterate until i exceeds N while (i <= N) { // Update sum ans += N / i; // Multiply i by K to // obtain next power of K i = i * K; } // Print the result cout << ans;}// Driver Codeint main(){ // Given N and K int N = 10, K = 2; findSum(N, K); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{ // Function to calculate sum of // quotients obtained by dividing // N by powers of K <= N static void findSum(int N, int K) { // Store the required sum int ans = 0; int i = 1; // Iterate until i exceeds N while (i <= N) { // Update sum ans += N / i; // Multiply i by K to // obtain next power of K i = i * K; } // Print the result System.out.println(ans); } // Driver Code public static void main(String[] args) { // Given N and K int N = 10, K = 2; findSum(N, K); }}// This code is contributed by shubhamsingh10 |
Python3
# Python3 program for the above approach# Function to calculate sum of# quotients obtained by dividing# N by powers of K <= Ndef findSum(N, K): # Store the required sum ans = 0 i = 1 # Iterate until i exceeds N while (i <= N): # Update sum ans += N // i # Multiply i by K to # obtain next power of K i = i * K # Print the result print (ans)# Driver Codeif __name__ == '__main__': # Given N and K N, K = 10, 2 findSum(N, K) # This code is contributed by mohit kumar 29. |
C#
// C# program for the above approach using System;class GFG{ // Function to calculate sum of// quotients obtained by dividing// N by powers of K <= Nstatic void findSum(int N, int K){ // Store the required sum int ans = 0; int i = 1; // Iterate until i exceeds N while (i <= N) { // Update sum ans += N / i; // Multiply i by K to // obtain next power of K i = i * K; } // Print the result Console.Write(ans);}// Driver code static void Main() { // Given N and K int N = 10, K = 2; findSum(N, K);}}// This code is contributed by code_hunt |
Javascript
<script>// javascript program for the above approach// Function to calculate sum of// quotients obtained by dividing// N by powers of K <= Nfunction findSum(N, K){ // Store the required sum var ans = 0; var i = 1; // Iterate until i exceeds N while (i <= N) { // Update sum ans += Math.floor(N / i); // Multiply i by K to // obtain next power of K i = i * K; } // Print the result document.write(ans);}// Driver Code // Given N and K var N = 10, K = 2; findSum(N, K); </script> |
18
Time Complexity: O(logK(N))
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
