Различные степени числа N такие, что сумма равна K

Опубликовано: 7 Января, 2022

Учитывая два числа N и K , задача состоит в том, чтобы вывести различные степени N, которые используются для получения суммы K. Если это невозможно, выведите -1 .
Примеры:

Input: N = 3, K = 40
Output: 0, 1, 2, 3
Explanation:
The value of N is 3.
3⁰ + 3¹ + 3² + 3³ = 40
Input: N = 4, K = 65
Output: 0, 3
The value of N is 4.
4⁰ + 4³ = 65
Input: N = 4, K = 18
Output: -1
Explanation:
It’s impossible to get 18 by adding the powers of 4.

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Наблюдение: одно наблюдение, которое необходимо сделать для любого произвольного числа a, состоит в том, что не может существовать числа больше, чем ^K, если все степени a от 0 до k-1 складываются с использованием каждой степени хотя бы один раз.
Пример: Пусть a = 3 и K = 4. Тогда:

3⁴ = 81.
3⁰ + 3¹ + 3² + 3³ = 40 which is less than 81(3⁴).

Naive Approach: By using the above observation, the naive approach can be formed. The idea is to continuously subtract the highest power of N not exceeding K from K until K reaches 0. If at any instance, K becomes equal to some power which was already subtracted from it previously, then it’s not possible to get the sum equal to K. Therefore, an array is used to keep a track of powers that have been subtracted from K.
Below is the implementation of the above approach:

C++

// C++ implementation to find distinct
// powers of N that add upto K
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the highest power
// of N not exceeding K
int highestPower(int n, int k)
{
    int i = 0;
    int a = pow(n, i);
 
    // Loop to find the highest power
    // less than K
    while (a <= k) {
        i += 1;
        a = pow(n, i);
    }
    return i - 1;
}
 
// Initializing the PowerArray
// with all 0"s.
int b[50] = { 0 };
 
// Function to print
// the distinct powers of N
// that add upto K
int PowerArray(int n, int k)
{
    while (k) {
 
        // Getting the highest
        // power of n before k
        int t = highestPower(n, k);
 
        // To check if the power
        // is being used twice or not
        if (b[t]) {
 
            // Print -1 if power
            // is being used twice
            cout << -1;
            return 0;
        }
 
        else
            // If the power is not visited,
            // then mark the power as visited
            b[t] = 1;
 
        // Decrementing the value of K
        k -= pow(n, t);
    }
 
    // Printing the powers of N
    // that sum up to K
    for (int i = 0; i < 50; i++) {
        if (b[i]) {
            cout << i << ", ";
        }
    }
}
 
// Driver code
int main()
{
    int N = 3;
    int K = 40;
    PowerArray(N, K);
    return 0;
}

Java

// Java implementation to find distinct
// powers of N that add upto K
 
class GFG{
  
// Function to return the highest power
// of N not exceeding K
static int highestPower(int n, int k)
{
    int i = 0;
    int a = (int) Math.pow(n, i);
  
    // Loop to find the highest power
    // less than K
    while (a <= k) {
        i += 1;
        a = (int) Math.pow(n, i);
    }
    return i - 1;
}
  
// Initializing the PowerArray
// with all 0"s.
static int b[] = new int[50];
  
// Function to print
// the distinct powers of N
// that add upto K
static int PowerArray(int n, int k)
{
    while (k>0) {
  
        // Getting the highest
        // power of n before k
        int t = highestPower(n, k);
  
        // To check if the power
        // is being used twice or not
        if (b[t]>0) {
  
            // Print -1 if power
            // is being used twice
            System.out.print(-1);
            return 0;
        }
  
        else
            // If the power is not visited,
            // then mark the power as visited
            b[t] = 1;
  
        // Decrementing the value of K
        k -= Math.pow(n, t);
    }
  
    // Printing the powers of N
    // that sum up to K
    for (int i = 0; i < 50; i++) {
        if (b[i] > 0) {
            System.out.print(i+ ", ");
        }
    }
    return 0;
}
  
// Driver code
public static void main(String[] args)
{
    int N = 3;
    int K = 40;
    PowerArray(N, K);
}
}
 
// This code contributed by Rajput-Ji

Python3

# Python 3 implementation to find distinct
# powers of N that add up to K
 
from math import pow
 
# Function to return the highest power
# of N not exceeding K
def highestPower(n,k):
    i = 0
    a = pow(n, i)
 
    # Loop to find the highest power
    # less than K
    while (a <= k):
        i += 1
        a = pow(n, i)
    return i - 1
 
# Initializing the PowerArray
# with all 0"s.
b = [0 for i in range(50)]
 
# Function to print
# the distinct powers of N
# that add upto K
def PowerArray(n, k):
    while (k):
        # Getting the highest
        # power of n before k
        t = highestPower(n, k)
 
        # To check if the power
        # is being used twice or not
        if (b[t]):
            # Print -1 if power
            # is being used twice
            print(-1)
            return 0
 
        else:
            # If the power is not visited,
            # then mark the power as visited
            b[t] = 1
 
        # Decrementing the value of K
        k -= pow(n, t)
 
    # Printing the powers of N
    # that sum up to K
    for i in range(50):
        if (b[i]):
            print(i,end = ", ")
 
# Driver code
if __name__ == "__main__":
    N = 3
    K = 40
    PowerArray(N, K)
     
# This code is contributed by Surendra_Gangwar

C#

     
// C# implementation to find distinct
// powers of N that add up to K
 
using System;
 
public class GFG{
 
// Function to return the highest power
// of N not exceeding K
static int highestPower(int n, int k)
{
    int i = 0;
    int a = (int) Math.Pow(n, i);
 
    // Loop to find the highest power
    // less than K
    while (a <= k) {
        i += 1;
        a = (int) Math.Pow(n, i);
    }
    return i - 1;
}
 
// Initializing the PowerArray
// with all 0"s.
static int []b = new int[50];
 
// Function to print
// the distinct powers of N
// that add upto K
static int PowerArray(int n, int k)
{
    while (k > 0) {
 
        // Getting the highest
        // power of n before k
        int t = highestPower(n, k);
 
        // To check if the power
        // is being used twice or not
        if (b[t] > 0) {
 
            // Print -1 if power
            // is being used twice
            Console.Write(-1);
            return 0;
        }
 
        else
            // If the power is not visited,
            // then mark the power as visited
            b[t] = 1;
 
        // Decrementing the value of K
        k -= (int)Math.Pow(n, t);
    }
 
    // Printing the powers of N
    // that sum up to K
    for (int i = 0; i < 50; i++) {
        if (b[i] > 0) {
            Console.Write(i+ ", ");
        }
    }
    return 0;
}
 
// Driver code
public static void Main(String[] args)
{
    int N = 3;
    int K = 40;
    PowerArray(N, K);
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
// Javascript implementation to find distinct
// powers of N that add upto K
 
// Function to return the highest power
// of N not exceeding K
function highestPower(n, k)
{
    let i = 0;
    let a = Math.pow(n, i);
  
    // Loop to find the highest power
    // less than K
    while (a <= k) {
        i += 1;
        a = Math.pow(n, i);
    }
    return i - 1;
}
  
// Initializing the PowerArray
// with all 0"s.
let b = Array.from({length: 50}, (_, i) => 0);
  
// Function to print
// the distinct powers of N
// that add upto K
function PowerArray(n, k)
{
    while (k>0) {
  
        // Getting the highest
        // power of n before k
        let t = highestPower(n, k);
  
        // To check if the power
        // is being used twice or not
        if (b[t]>0) {
  
            // Prlet -1 if power
            // is being used twice
            document.write(-1);
            return 0;
        }
  
        else
            // If the power is not visited,
            // then mark the power as visited
            b[t] = 1;
  
        // Decrementing the value of K
        k -= Math.pow(n, t);
    }
  
    // Prleting the powers of N
    // that sum up to K
    for (let i = 0; i < 50; i++) {
        if (b[i] > 0) {
            document.write(i+ ", ");
        }
    }
    return 0;
}
 
// Driver Code
     
    let N = 3;
    let K = 40;
    PowerArray(N, K);
         
</script>

Output:

0, 1, 2, 3,

Сложность времени: O ((log N) ² )

Время, затраченное на то, чтобы узнать силу, - это Журнал (N) .
Кроме того, для K используется еще один цикл Log (N).
Итак, общая временная сложность Log (N) ²

Эффективный подход: можно сделать еще одно наблюдение : для того, чтобы K было суммой мощностей N, которые можно использовать только один раз, K% N должен быть либо 1, либо 0 (1 из-за N ⁰ ). Следовательно, если ( K% N ) выходит что-либо, кроме 0 или 1, можно сделать вывод, что невозможно получить сумму K.
Следовательно, используя приведенное выше наблюдение, можно выполнить следующие шаги для вычисления ответа:

Сначала счетчик инициализируется 0.
Если (K% N) = 0 , то счетчик увеличивается на 1, а K обновляется до K / N.
Если K% N = 1 , то частотный массив f [count] увеличивается на 1, а K обновляется до K - 1 .
Если в какой-то момент f [count] окажется больше 1, тогда верните -1 (потому что одну и ту же мощность нельзя использовать дважды).

Below is the implementation of the above approach:

C++

// C++ implementation to find out
// the powers of N that add upto K
 
#include <bits/stdc++.h>
using namespace std;
 
// Initializing the PowerArray
// with all 0"s
int b[50] = { 0 };
 
// Function to find the powers of N
// that add up to K
int PowerArray(int n, int k)
{
 
    // Initializing the counter
    int count = 0;
 
    // Executing the while
    // loop until K is
    // greater than 0
    while (k) {
        if (k % n == 0) {
            k /= n;
            count++;
        }
 
        // If K % N == 1,
        // then the power array
        // is incremented by 1
        else if (k % n == 1) {
            k -= 1;
            b[count]++;
 
            // Checking if any power is
            // occurred more than once
            if (b[count] > 1) {
                cout << -1;
                return 0;
            }
        }
 
        // For any other value, the sum of
        // powers cannot be added up to K
   &nb
            

                    
                                            Олимпиады по программированию
                                    
РЕКОМЕНДУЕМЫЕ СТАТЬИНастройка Sublime Text для соревновательного программирования (C++) с использованием плагина Fast Olympic Coding
8 Января, 2023
Минимизируйте длину массива, многократно удаляя элементы, которые меньше, чем следующий элемент
19 Сентября, 2022
Задача коммивояжера Bitonic
19 Сентября, 2022
Количество суперстрок в заданном массиве строк
19 Сентября, 2022
Количество чередующихся подстрок из заданной двоичной строки
19 Сентября, 2022
Максимальное удаление мячей как минимум двух разных типов
19 Сентября, 2022
Общее время, необходимое для прохождения пути, обозначенного данной строкой
19 Сентября, 2022
Советы и рекомендации Python для соревновательного программирования
19 Сентября, 2022


    


        
            
                
                    
                        
                        < PROGLER >
                    
                
                
                    
                        Общее
                        
                        Контакты
                        Политика конфиденциальности
                    
                    
                        Обучение
                        Блог
                    
                
            
            
                © progler.ru 2024. Все права защищены.