970. Powerful Integers

LeetCode medium оригинал: C# #csharp #hash-table #leetcode #math #medium

LeetCode Static

Даны три целых числа x, y и bound. Верните список всех мощных чисел, которые имеют значение меньше или равное bound.

Целое число является мощным, если оно может быть представлено как x^i + y^j для некоторых целых чисел i >= 0 и j >= 0.

Вы можете вернуть ответ в любом порядке. В вашем ответе каждое значение должно встречаться не более одного раза.

Пример:

Input: x = 2, y = 3, bound = 10

Output: [2,3,4,5,7,9,10]

Explanation:

2 = 20 + 30

3 = 21 + 30

4 = 20 + 31

5 = 21 + 31

7 = 22 + 31

9 = 23 + 30

10 = 20 + 32

C# решение

сопоставлено/оригинал

using System;
using System.Collections.Generic;
public class Solution {
    public IList<int> PowerfulIntegers(int x, int y, int bound) {
        int a = x == 1 ? bound : (int)(Math.Log(bound) / Math.Log(x));
        int b = y == 1 ? bound : (int)(Math.Log(bound) / Math.Log(y));
        HashSet<int> powerfulIntegers = new HashSet<int>();
        for (int i = 0; i <= a; i++) {
            for (int j = 0; j <= b; j++) {
                int value = (int)Math.Pow(x, i) + (int)Math.Pow(y, j);
                if (value <= bound) {
                    powerfulIntegers.Add(value);
                }
                if (y == 1) {
                    break;
                }
            }
            if (x == 1) {
                break;
            }
        }
        return new List<int>(powerfulIntegers);
    }
}

C++ решение

auto-draft, проверить перед отправкой

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public vector<int> PowerfulIntegers(int x, int y, int bound) {
        int a = x == 1 ? bound : (int)(Math.Log(bound) / Math.Log(x));
        int b = y == 1 ? bound : (int)(Math.Log(bound) / Math.Log(y));
        HashSet<int> powerfulIntegers = new HashSet<int>();
        for (int i = 0; i <= a; i++) {
            for (int j = 0; j <= b; j++) {
                int value = (int)Math.Pow(x, i) + (int)Math.Pow(y, j);
                if (value <= bound) {
                    powerfulIntegers.push_back(value);
                }
                if (y == 1) {
                    break;
                }
            }
            if (x == 1) {
                break;
            }
        }
        return new List<int>(powerfulIntegers);
    }
}

Java решение

сопоставлено/оригинал

class Solution {
    public List<Integer> powerfulIntegers(int x, int y, int bound) {
        int a = x == 1 ? bound : (int) (Math.log(bound) / Math.log(x));
        int b = y == 1 ? bound : (int) (Math.log(bound) / Math.log(y));
        HashSet<Integer> powerfulIntegers = new HashSet<Integer>();

        for (int i = 0; i <= a; i++) {
            for (int j = 0; j <= b; j++) {
                int value = (int) Math.pow(x, i) + (int) Math.pow(y, j);
                if (value <= bound) {
                    powerfulIntegers.add(value);
                }
                if (y == 1) {
                    break;
                }
            }
            if (x == 1) {
                break;
            }
        }

        return new ArrayList<Integer>(powerfulIntegers);
    }
}

JavaScript решение

сопоставлено/оригинал

var powerfulIntegers = function(x, y, bound) {
    const a = x === 1 ? bound : Math.floor(Math.log(bound) / Math.log(x));
    const b = y === 1 ? bound : Math.floor(Math.log(bound) / Math.log(y));
    const powerfulIntegers = new Set();

    for (let i = 0; i <= a; i++) {
        for (let j = 0; j <= b; j++) {
            const value = Math.pow(x, i) + Math.pow(y, j);
            if (value <= bound) {
                powerfulIntegers.add(value);
            }
            if (y === 1) break;
        }
        if (x === 1) break;
    }

    return Array.from(powerfulIntegers);
};

Python решение

сопоставлено/оригинал

class Solution:
    def powerfulIntegers(self, x, y, bound):
        a = bound if x == 1 else int(math.log(bound) / math.log(x))
        b = bound if y == 1 else int(math.log(bound) / math.log(y))
        powerful_integers = set()

        for i in range(a + 1):
            for j in range(b + 1):
                value = x ** i + y ** j
                if value <= bound:
                    powerful_integers.add(value)
                if y == 1: break
            if x == 1: break

        return list(powerful_integers)

Algorithm

Вычислите степени a и b как логарифмы bound по основаниям x и y соответственно. Создайте множество powerfulIntegers для хранения результатов.

Используйте вложенные циклы, где внешний цикл проходит от 0 до a, а внутренний цикл от 0 до b. На каждом шаге вычисляйте x^i + y^j и, если значение меньше или равно bound, добавляйте его в множество powerfulIntegers.

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.