Solution: Powerful Integers

Leetcode Solutions (161 Part Series)

1 Solution: Next Permutation
2 Solution: Trim a Binary Search Tree
… 157 more parts…
3 Leetcode Solutions Index
4 Solution: Minimize Deviation in Array
5 Solution: Vertical Order Traversal of a Binary Tree
6 Solution: Count Ways to Make Array With Product
7 Solution: Smallest String With A Given Numeric Value
8 Solution: Linked List Cycle
9 Solution: Path With Minimum Effort
10 Solution: Concatenation of Consecutive Binary Numbers
11 Solution: Minimum Operations to Make a Subsequence
12 Solution: Longest Harmonious Subsequence
13 Solution: Simplify Path
14 Solution: Building Boxes
15 Solution: Decode XORed Permutation
16 Solution: Binary Tree Right Side View
17 Solution: Find Kth Largest XOR Coordinate Value
18 Solution: Change Minimum Characters to Satisfy One of Three Conditions
19 Solution: Shortest Distance to a Character
20 Solution: Peeking Iterator
21 Solution: Convert BST to Greater Tree
22 Solution: Copy List with Random Pointer
23 Solution: Valid Anagram
24 Solution: Number of Steps to Reduce a Number to Zero
25 Solution: Shortest Path in Binary Matrix
26 Solution: Is Graph Bipartite?
27 Solution: Maximum Score From Removing Substrings (ver. 1)
28 Solution: Maximum Score From Removing Substrings (ver. 2)
29 Solution: Sort the Matrix Diagonally
30 Solution: The K Weakest Rows in a Matrix (ver. 1)
31 Solution: The K Weakest Rows in a Matrix (ver. 2)
32 Solution: Letter Case Permutation
33 Solution: Container With Most Water
34 Solution: Arithmetic Slices
35 Solution: Minimum Remove to Make Valid Parentheses
36 Solution: Roman to Integer
37 Solution: Broken Calculator
38 Solution: Find the Most Competitive Subsequence
39 Solution: Longest Word in Dictionary through Deleting
40 Solution: Search a 2D Matrix II
41 Solution: Score of Parentheses
42 Solution: Shortest Unsorted Continuous Subarray
43 Solution: Validate Stack Sequences
44 Solution: Divide Two Integers (ver. 1)
45 Solution: Divide Two Integers (ver. 2)
46 Solution: Maximum Frequency Stack
47 Solution: Distribute Candies
48 Solution: Set Mismatch (ver. 1)
49 Solution: Set Mismatch (ver. 2)
50 Solution: Missing Number
51 Solution: Intersection of Two Linked Lists
52 Solution: Average of Levels in Binary Tree
53 Solution: Short Encoding of Words (ver. 1)
54 Solution: Design HashMap (ver. 1)
55 Solution: Short Encoding of Words (ver. 2)
56 Solution: Design HashMap (ver. 2)
57 Solution: Remove Palindromic Subsequences
58 Solution: Add One Row to Tree
59 Solution: Integer to Roman
60 Solution: Coin Change
61 Solution: Check If a String Contains All Binary Codes of Size K
62 Solution: Binary Trees With Factors
63 Solution: Swapping Nodes in a Linked List
64 Solution: Encode and Decode TinyURL
65 Solution: Best Time to Buy and Sell Stock with Transaction Fee
66 Solution: Generate Random Point in a Circle
67 Solution: Wiggle Subsequence
68 Solution: Keys and Rooms
69 Solution: Design Underground System
70 Solution: Reordered Power of 2
71 Solution: Vowel Spellchecker
72 Solution: 3Sum With Multiplicity
73 Solution: Advantage Shuffle
74 Solution: Pacific Atlantic Water Flow
75 Solution: Word Subsets
76 Solution: Palindromic Substrings
77 Solution: Reconstruct Original Digits from English
78 Solution: Flip Binary Tree To Match Preorder Traversal
79 Solution: Russian Doll Envelopes
80 Solution: Stamping The Sequence
81 Solution: Palindrome Linked List
82 Solution: Ones and Zeroes
83 Solution: Longest Valid Parentheses
84 Solution: Design Circular Queue
85 Solution: Global and Local Inversions
86 Solution: Minimum Operations to Make Array Equal
87 Solution: Determine if String Halves Are Alike
88 Solution: Letter Combinations of a Phone Number
89 Solution: Verifying an Alien Dictionary
90 Solution: Longest Increasing Path in a Matrix
91 Solution: Deepest Leaves Sum
92 Solution: Beautiful Arrangement II
93 Solution: Flatten Nested List Iterator
94 Solution: Partition List
95 Solution: Fibonacci Number
96 Solution: Remove All Adjacent Duplicates in String II
97 Solution: Number of Submatrices That Sum to Target
98 Solution: Remove Nth Node From End of List
99 Solution: Combination Sum IV
100 Solution: N-ary Tree Preorder Traversal
101 Solution: Triangle
102 Solution: Brick Wall
103 Solution: Count Binary Substrings
104 Solution: Critical Connections in a Network
105 Solution: Rotate Image
106 Solution: Furthest Building You Can Reach
107 Solution: Power of Three
108 Solution: Unique Paths II
109 Solution: Find First and Last Position of Element in Sorted Array
110 Solution: Powerful Integers
111 Solution: Prefix and Suffix Search
112 Solution: Course Schedule III
113 Solution: Running Sum of 1d Array
114 Solution: Non-decreasing Array
115 Solution: Jump Game II
116 Solution: Convert Sorted List to Binary Search Tree
117 Solution: Delete Operation for Two Strings
118 Solution: Super Palindromes
119 Solution: Construct Target Array With Multiple Sums
120 Solution: Count Primes
121 Solution: Maximum Points You Can Obtain from Cards
122 Solution: Range Sum Query 2D – Immutable
123 Solution: Ambiguous Coordinates
124 Solution: Flatten Binary Tree to Linked List
125 Solution: Valid Number
126 Solution: Binary Tree Cameras
127 Solution: Longest String Chain
128 Solution: Find Duplicate File in System
129 Solution: Minimum Moves to Equal Array Elements II
130 Solution: Binary Tree Level Order Traversal
131 Solution: Find and Replace Pattern
132 Solution: N-Queens
133 Solution: To Lower Case
134 Solution: Evaluate Reverse Polish Notation
135 Solution: Partitioning Into Minimum Number Of Deci-Binary Numbers
136 Solution: Maximum Product of Word Lengths
137 Solution: Maximum Erasure Value
138 Solution: N-Queens II
139 Solution: Maximum Gap
140 Solution: Search Suggestions System
141 Solution: Max Area of Island
142 Solution: Interleaving String
143 Solution: Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts
144 Solution: Open the Lock
145 Solution: Maximum Performance of a Team
146 Solution: Longest Consecutive Sequence
147 Solution: Min Cost Climbing Stairs
148 Solution: Construct Binary Tree from Preorder and Inorder Traversal
149 Solution: Jump Game VI
150 Solution: My Calendar I
151 Solution: Stone Game VII
152 Solution: Minimum Number of Refueling Stops
153 Solution: Palindrome Pairs
154 Solution: Maximum Units on a Truck
155 Solution: Matchsticks to Square
156 Solution: Generate Parentheses
157 Solution: Number of Subarrays with Bounded Maximum
158 Solution: Swim in Rising Water
159 Solution: Pascal’s Triangle
160 Solution: Out of Boundary Paths
161 Solution: Redundant Connection

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode’s forums.

Leetcode Problem #970 (Medium): Powerful Integers

Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

Given three integers x, y, and bound, return a list of all the powerful integers that have a value less than or equal to bound.

An integer is powerful if it can be represented as xi + yj for some integers i >= 0 and j >= 0.

You may return the answer in any order. In your answer, each value should occur at most once.

Examples:

Example 1:

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

Example 2:

Input: x = 3, y = 5, bound = 15

Output: [2,4,6,8,10,14]

Example 1:
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

Example 2:
Input:	x = 3, y = 5, bound = 15
Output:	[2,4,6,8,10,14]

Constraints:

1 <= x, y <= 100

0 <= bound <= 10^6

Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

This problem is a pretty straightforward one. Since we need to return all powerful integers and not just a count of them, there aren’t many shortcuts we can take; we’ll have to actually come up with the solution iteratively with nested loops.

First, we can use a set structure (ans) to prevent duplicate answers. Then we can have our nested loops increment the power of the x and y values while adding the appropriate results to our set.

One somewhat tricky situation occurs when one or more of the values is a 1, as that power will continue to be 1 forever, regardless of the exponent. To deal with that, we can force each nested loop to break after the first iteration if its original value was a 1.

Once we’ve iterated over all possible combinations, we can convert ans to an array and return it.

Implementation:

There are only minor differences in the code of each language.

Javascript Code:

(Jump to: Problem Description || Solution Idea)

var powerfulIntegers = function(x, y, bound) {
    let ans = new Set()
    for (let xi = 1; xi < bound; xi *= x) {
        for (let yj = 1; xi + yj <= bound; yj *= y) {
            ans.add(xi + yj)
            if (y === 1) break
        }
        if (x === 1) break
    }
    return Array.from(ans)
}

Enter fullscreen mode Exit fullscreen mode

Python Code:

(Jump to: Problem Description || Solution Idea)

class Solution:
    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:
        ans, xi = set(), 1
        while xi < bound:
            yj = 1
            while xi + yj <= bound:
                ans.add(xi + yj)
                if y == 1: break
                yj *= y
            if x == 1: break
            xi *= x
        return list(ans)

Enter fullscreen mode Exit fullscreen mode

Java Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
    public List<Integer> powerfulIntegers(int x, int y, int bound) {
        Set<Integer> ans = new HashSet<>();
        for (int xi = 1; xi < bound; xi *= x) {
            for (int yj = 1; xi + yj <= bound; yj *= y) {
                ans.add(xi + yj);
                if (y == 1) break;
            }
            if (x == 1) break;
        }
        return new ArrayList<Integer>(ans);
    }
}

Enter fullscreen mode Exit fullscreen mode

C++ Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
public:
    vector<int> powerfulIntegers(int x, int y, int bound) {
        unordered_set<int> ans;
        for (int xi = 1; xi < bound; xi *= x) {
            for (int yj = 1; xi + yj <= bound; yj *= y) {
                ans.insert(xi + yj);
                if (y == 1) break;
            }
            if (x == 1) break;
        }
        return vector<int>(ans.begin(), ans.end());
    }
};

Enter fullscreen mode Exit fullscreen mode

Leetcode Solutions (161 Part Series)

原文链接：Solution: Powerful Integers

文章版权声明 1、本网站名称：拾光赋
2、本站永久网址：https://www.blogs.ink
3、本网站的文章部分内容可能来源于网络，仅供大家学习与参考，如有侵权，请联系站长QQ：805375623进行删除处理。
4、本站一切资源不代表本站立场，并不代表本站赞同其观点和对其真实性负责。
5、本站一律禁止以任何方式发布或转载任何违法的相关信息，访客发现请向站长举报
6、本站资源大多存储在云盘，如发现链接失效，请联系我们我们会第一时间更新。

THE END