Given a number N, and an integer K. The task is to distribute N in a sequence such that the first K numbers of the sequence is 20, the next K numbers are 21, and so on such that the sum of the sequence is at most N. Find the largest size of the sequence.
Examples:
Input: N = 35, K = 5
Output: 15
Explanation: The sequence is 1 1 1 1 1 2 2 2 2 2 4 4 4 4 4.
The summation of the sequence is 35.Input: N = 16, K = 3
Output: 8
Explanation: The sequence is 1 1 1 2 2 2 4.
The summation of the sequence is 13, which is less that 16
Approach: Follow the below steps to solve the problem:
- Let variable ans store the output of the program.
- Take a loop from 1 to i, which calculates the size of the sequence up to which K*pow(2, i) < N. By adding K to ans and subtracting K*pow(2, i) from N in each loop.
- The size of the remaining sequence is calculated by adding N/pow(2, i) to ans.
Below is the implementation of the above approach:
C++
// C++ code to implement the above approach#include <bits/stdc++.h>using namespace std;// Function to find the size of sequenceint get(int N, int K){ int ans = 0; int i = 0; // Loop to calculate size of sequence // upto which K*pow(2, i) < N. while (K * pow(2, i) < N) { N -= (K * pow(2, i)); i++; ans += K; } // Calculate Size of remaining sequence ans += N / (pow(2, i)); return ans;}// Driver codeint main(){ int N, K; N = 35; K = 5; cout << get(N, K); return 0;} |
Java
// Java code to implement the above approachclass GFG { // Function to find the size of sequence static int get(int N, int K) { int ans = 0; int i = 0; // Loop to calculate size of sequence // upto which K*pow(2, i) < N. while (K * (int)Math.pow(2, i) < N) { N -= (K * (int)Math.pow(2, i)); i++; ans += K; } // Calculate Size of remaining sequence ans += N / (int)(Math.pow(2, i)); return ans; } // Driver code public static void main(String[] args) { int N, K; N = 35; K = 5; System.out.print(get(N, K)); }}// This code is contributed by ukasp. |
Python3
# Python code to implement the above approach# Function to find the size of sequencedef get (N, K): ans = 0; i = 0; # Loop to calculate size of sequence # upto which K*pow(2, i) < N. while (K * (2 ** i) < N): N -= (K * (2 ** i)); i += 1 ans += K; # Calculate Size of remaining sequence ans += (N // (2 ** i)); return ans;# Driver codeN = 35;K = 5;print(get(N, K));# This code is contributed by Saurabh Jaiswal |
C#
// C# code to implement the above approachusing System;class GFG{ // Function to find the size of sequence static int get(int N, int K) { int ans = 0; int i = 0; // Loop to calculate size of sequence // upto which K*pow(2, i) < N. while (K * (int)Math.Pow(2, i) < N) { N -= (K * (int)Math.Pow(2, i)); i++; ans += K; } // Calculate Size of remaining sequence ans += N / (int)(Math.Pow(2, i)); return ans; } // Driver code public static void Main() { int N, K; N = 35; K = 5; Console.Write(get(N, K)); }}// This code is contributed b Samim Hossain Mondal. |
Javascript
<script> // JavaScript code to implement the above approach // Function to find the size of sequence const get = (N, K) => { let ans = 0; let i = 0; // Loop to calculate size of sequence // upto which K*pow(2, i) < N. while (K * Math.pow(2, i) < N) { N -= (K * Math.pow(2, i)); i++; ans += K; } // Calculate Size of remaining sequence ans += parseInt(N / (Math.pow(2, i))); return ans; } // Driver code let N, K; N = 35; K = 5; document.write(get(N, K));// This code is contributed by rakeshsahni</script> |
Output
15
Time Complexity: O(log(N)) where the base of log is K
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
