Bir n sayısı verildiğinde, bu sayıyı iki küpün toplamı olarak temsil edebilecek iki çift bulun. Başka bir deyişle, verilen n sayısını şu şekilde ifade edebilecek iki (a b) ve (c d) çifti bulun.
n = a^3 + b^3 = c^3 + d^3
burada a b c ve d dört farklı sayıdır.
Örnekler:
10/100,00
Input: N = 1729 Output: (1 12) and (9 10) Explanation: 1729 = 1^3 + 12^3 = 9^3 + 10^3 Input: N = 4104 Output: (2 16) and (9 15) Explanation: 4104 = 2^3 + 16^3 = 9^3 + 15^3 Input: N = 13832 Output: (2 24) and (18 20) Explanation: 13832 = 2^3 + 24^3 = 18^3 + 20^3
Kısıtlamayı karşılayan herhangi bir n sayısı iki farklı (a b) ve (c d) çiftine sahip olacaktır, öyle ki a b c ve d'nin tümü aşağıdakilerden küçüktür N1/3 . Fikir çok basit. Aşağıdaki sayılardan daha küçük sayıların oluşturduğu her farklı (x y) çifti için N1/3 eğer bunların toplamı (x3+ ve3) verilen sayıya eşitse bunları sum anahtar olarak kullanarak bir karma tablosunda saklarız. Toplamları verilen sayıya eşit olan çiftler tekrar görünürse, her iki çifti de yazdırırız.
java kırpma dizesi
1) Create an empty hash map say s. 2) cubeRoot = n1/3 3) for (int x = 1; x < cubeRoot; x++) for (int y = x + 1; y <= cubeRoot; y++) int sum = x3 + y3; if (sum != n) continue; if sum exists in s we found two pairs with sum print the pairs else insert pair(x y) in s using sum as key
Aşağıda yukarıdaki fikrin uygulanması yer almaktadır -
C++
// C++ program to find pairs that can represent // the given number as sum of two cubes #include
// Java program to find pairs that can represent // the given number as sum of two cubes import java.util.*; class GFG { static class pair { int first second; public pair(int first int second) { this.first = first; this.second = second; } } // Function to find pairs that can represent // the given number as sum of two cubes static void findPairs(int n) { // find cube root of n int cubeRoot = (int) Math.pow(n 1.0/3.0); // create an empty map HashMap<Integer pair> s = new HashMap<Integer pair>(); // Consider all pairs such with values less // than cuberoot for (int x = 1; x < cubeRoot; x++) { for (int y = x + 1; y <= cubeRoot; y++) { // find sum of current pair (x y) int sum = x*x*x + y*y*y; // do nothing if sum is not equal to // given number if (sum != n) continue; // if sum is seen before we found two pairs if (s.containsKey(sum)) { System.out.print('(' + s.get(sum).first+ ' ' + s.get(sum).second+ ') and (' + x+ ' ' + y+ ')' +'n'); } else // if sum is seen for the first time s.put(sum new pair(x y)); } } } // Driver code public static void main(String[] args) { int n = 13832; findPairs(n); } } // This code is contributed by PrinciRaj1992
# Python3 program to find pairs # that can represent the given # number as sum of two cubes # Function to find pairs that # can represent the given number # as sum of two cubes def findPairs(n): # Find cube root of n cubeRoot = pow(n 1.0 / 3.0); # Create an empty map s = {} # Consider all pairs such with # values less than cuberoot for x in range(int(cubeRoot)): for y in range(x + 1 int(cubeRoot) + 1): # Find sum of current pair (x y) sum = x * x * x + y * y * y; # Do nothing if sum is not equal to # given number if (sum != n): continue; # If sum is seen before we # found two pairs if sum in s.keys(): print('(' + str(s[sum][0]) + ' ' + str(s[sum][1]) + ') and (' + str(x) + ' ' + str(y) + ')' + 'n') else: # If sum is seen for the first time s[sum] = [x y] # Driver code if __name__=='__main__': n = 13832 findPairs(n) # This code is contributed by rutvik_56
// C# program to find pairs that can represent // the given number as sum of two cubes using System; using System.Collections.Generic; class GFG { class pair { public int first second; public pair(int first int second) { this.first = first; this.second = second; } } // Function to find pairs that can represent // the given number as sum of two cubes static void findPairs(int n) { // find cube root of n int cubeRoot = (int) Math.Pow(n 1.0/3.0); // create an empty map Dictionary<int pair> s = new Dictionary<int pair>(); // Consider all pairs such with values less // than cuberoot for (int x = 1; x < cubeRoot; x++) { for (int y = x + 1; y <= cubeRoot; y++) { // find sum of current pair (x y) int sum = x*x*x + y*y*y; // do nothing if sum is not equal to // given number if (sum != n) continue; // if sum is seen before we found two pairs if (s.ContainsKey(sum)) { Console.Write('(' + s[sum].first+ ' ' + s[sum].second+ ') and (' + x+ ' ' + y+ ')' +'n'); } else // if sum is seen for the first time s.Add(sum new pair(x y)); } } } // Driver code public static void Main(String[] args) { int n = 13832; findPairs(n); } } // This code is contributed by PrinciRaj1992
// JavaScript program to find pairs that can represent // the given number as sum of two cubes // Function to find pairs that can represent // the given number as sum of two cubes function findPairs(n){ // find cube root of n let cubeRoot = Math.floor(Math.pow(n 1/3)); // create an empty map let s = new Map(); // Consider all pairs such with values less // than cuberoot for (let x = 1; x < cubeRoot; x++){ for (let y = x + 1; y <= cubeRoot; y++){ // find sum of current pair (x y) let sum = x*x*x + y*y*y; // do nothing if sum is not equal to // given number if (sum != n){ continue; } // if sum is seen before we found two pairs if (s.has(sum)){ console.log('(' s.get(sum)[0] '' s.get(sum)[1] ') and ('x'' y')'); } else{ // if sum is seen for the first time s.set(sum [x y]); } } } } // Driver function { let n = 13832; findPairs(n); } // The code is contributed by Gautam goel (gautamgoel962)
Çıkış:
(2 24) and (18 20)
Zaman Karmaşıklığı yukarıdaki çözümün O(n) olduğu2/3) O(n)'den çok daha küçüktür.
Java dizeyi tam sayıya dönüştürür
Yukarıdaki problemi O(n) cinsinden çözebilir miyiz?1/3) zaman? Bir sonraki yazıda bunu tartışacağız.