We are given a number N and we have to find pairs i and j where i^3=j^2

For example, let N=50 so for this we will have 3 pairs (1,1),(4,8),(9,27) basically, we have to find pairs where the cube of one number is the same as the square of the other number in a given pair

the constraint is

• 1<N<10^6
• 1<i,j<N

Naive approach use 2 for loops iterate through each element and get those pairs where cube is equal to sum time complexity is O(n*2)

def get_pair(N):
    for i in range(1,N):
        for j in range(1,N):
            if i*i*i==j*j:
                print(i,j)
N=50
get_pair(N)

what will be an optimal way to solve this problem with a better time complexity?

CodePudding user response：

You do this with one loop (and minimal iterations) if you know that that pairs (x, y) are always y = x * i, this means you can use:

def get_pair(N):
    i = 1
    a = 1
    b = -1
    while a * i < N:
        b = a * i
        print(a,b)
        i  = 1
        a = i**2

N=50
get_pair(N)

This gets all 3 pairs:

1 1
4 8
9 27

In only 3 total iterations.

CodePudding user response：

Since you're working with integers, if there exists some number M = i^3 = j^2 for i and j between 1 and N, then that means there exists a k such that M = k^6. To find i and j, simply compare the representations of M:

(1) M = k^6 = i^3 = (k^2)^3 therefore i = k^2

(2) M = k^6 = j^2 = (k^3)^2 therefore j = k^3

Since j is always greater than or equal to i, you only need to check if 1 < k^3 < N. In other words, k should be less than the cube root of N.

Note that 100 isn't a valid candidate for k because that would make j less than or equal to N instead of strictly less than N (if we're going with N = 10^6).

So to get the list of tuples that satisfy your problem, find the values of k such that 1 < k^3 < N and return its square and cube in a tuple.

import math
from typing import List, Tuple

N: int = 10**6
pairs: List[Tuple[int, int]] = [(k * k, k * k * k) for k in range(2, math.ceil(N**(1 / 3)))]
print(pairs)

This is a list comprehension, a shorthand for a for-loop.

I'm basically asking Python to generate a list of tuples over an index k that falls in the range defined as range(2, math.ceil(N**(1 / 3)). That range is exactly the first column of the table above.

Then, for every k in that range I make a tuple of which the first item is k^2 and the second item is k^3, just like the last two columns of the table.

Also threw in the typing library in there for good measure. Clear code is good code, even for something as small as this. Python can figure out that pairs is a list of tuples without anyone telling it, but this way I've explicitly enforced that variable to be a list of tuples to avoid any confusion when someone tries to give it a different value or isn't sure what the variable contains.

CodePudding user response：

Another naive approach could be to use the "basic" values ?

def get_pair(N):
    for i in range(N):
        if(i**3 > MAX):
            break    # Limit to the max you want, and i**3 > i**2 if i > 1

        print(i**2, i**3)

Time complexity seems to be O(n) (Not an expert, so correct me if i'm wrong)

This is made so that the first element cubed == second element squared:

first = a^2
second = a^3

first^3 = a^(2*3) = a^6
second^2 = a^(3*2) = a^6

CodePudding user response：

You can use itertool's combinations_with_replacement function.

from itertools import combinations_with_replacement as combinations

def get_pair(N):
    for i, j in combinations(range(1,N), 2):
        if i*i*i==j*j:
            print(i,j)
N=50
get_pair(N)

CodePudding user response：

A pretty fast and readable solution would be to just iterate over all cubic numbers and their roots, then check if said cube is also a square number.

from typing import Tuple
def get_pair(N):
    def is_and_get_square(target, start) -> Tuple[bool, int]:
        j, j2 = start, start * start
        while j2 < target:
            j  = 1
            j2 = j * j
            
        return (True, j) if j2 == target else (False, None) 
        
    result = []
    i, i3 = 1, 1
    while i3 < N:
        check = is_and_get_square(i3, i)
        if check[0]:
            result.append((i, check[1]))
        
        i  = 1
        i3 = i ** 3
        
    return result
    
print(get_pair(10 ** 6))

Output

[(1, 1), (4, 8), (9, 27), (16, 64), (25, 125), (36, 216), (49, 343), (64, 512), (81, 729)]

Time Complexity: O(log(N) * log(10**6)) = O(log(N))