Interview Question
Country: United States
I think function will take only 'A' and 'N' as input. If this is the case then it is simple.
Sort the Array [O(nlogn)]
Put one pointer at the beginning and one pointer at the end.
Now add cubes of two numbers pointed by two pointers.
If sum is greater than 'A', then move last pointer one step towards left side.
If sum is smaller than 'A', then move first pointer one step towards right side.
Otherwise, you will have one pair.
But my concern is there will only be one pair if all numbers are positive as given in question.
public class QuestionApril22_1 {
public static boolean AllXYSatisfyEquation(int x[], int y[], int N, int A)
{
int lengthOfXArray = x.length;
int lengthOfYArray = y.length;
if (lengthOfXArray != lengthOfYArray)
return false;
if ((lengthOfXArray == lengthOfYArray) && (lengthOfXArray != N))
return false;
for (int i=0; i<lengthOfXArray; i++)
{
if ((Math.pow(x[i],3) + Math.pow(y[i],3)) != A)
return false;
}
return true;
}
public static void main(String[] args)
{
int x[] = {1,1,1};
int y[] = {1,1,1};
int N = 3;
int A = 2;
System.out.println(AllXYSatisfyEquation(x,y,N,A));
}
}
Here is a C# solution:
using System;
using System.Collections.Generic;
// en.wikipedia.org/wiki/Taxicab_number
// In mathematics, the N-th taxicab number, typically denoted Ta(n) or Taxicab(n),
// is defined as the smallest number that can be expressed as a sum of
// two positive algebraic cubes in 'N' distinct ways
namespace MathTrivia
{
class TaxicabNumber
{
static Tuple<int, int>[] solutions;
static bool Question(UInt64 A, UInt32 N)
{
// Step 1. Calculate 'max' as the largest value that when cubed is less than A
// And 'halfmax' as the largest value that when cubes is less than (A/2)
int max = 0;
int halfmax = 0;
{
UInt64 halfA = A / 2;
UInt64 t;
do
{
max++; // Test the next integer
t = (UInt64)max;
t = t * t * t;
if (t < halfA)
halfmax = max;
} while (t < A);
max--; // backup by one since last cube was too large
}
// Step 2. Precompute the cubes that we will need.
// Allocate and initialize an array of all cubes for 0..max
// Allocate a Map that given a UInt64 returns the cube root if one exists.
// The Map only needs to contain the cubes that are greater or equal to A/2
UInt64[] cubes = new UInt64[halfmax+1];
Dictionary<UInt64,int> roots = new Dictionary<UInt64,int>(max-halfmax+1);
for (int i = 0; i <= max; i++)
{
UInt64 t = (UInt64)i;
t = t * t * t;
// Add t to the cubes[] or the roots Map, or both when i == halfmax
if (i <= halfmax)
{
cubes[i] = t;
}
if (i >= halfmax)
{
roots.Add(t, i);
}
}
// Step 3. Search the range of integers that could satify the equation x^3 + y^3 == A
//
UInt64 numSolutions = 0;
for (int x = 0; x <= halfmax; x++)
{
UInt64 x3 = cubes[x];
UInt64 remaining = A - x3;
int y;
if (roots.TryGetValue(remaining, out y))
{
// the pair <x,y> satisfies the equation.
if (solutions == null)
{
solutions = new Tuple<int, int>[N];
}
solutions[numSolutions] = new Tuple<int, int>(x, y);
numSolutions++;
if (numSolutions >= N)
return true;
}
}
// We only found 'numSolutions', we didn't reach N
return false;
}
static void Main(string[] args)
{
UInt64 A;
UInt32 N;
if (args.Length == 0)
{
A = 48988659276962496;
N = 5;
Console.WriteLine("Sample example, let A=" + A + " and N=" + N);
}
else
{
if (args.Length != 2)
{
Console.WriteLine("Usage: Program A, N");
}
if (UInt64.TryParse(args[0], out A))
{
Console.WriteLine("Usage: Program >>A<<, N");
}
if (UInt32.TryParse(args[1], out N))
{
Console.WriteLine("Usage: Program A, >>N<<");
}
}
bool result = Question(A, N);
Console.WriteLine("Question(A is " + A + ", N is " + N + ") is " + result);
if (result)
{
Console.WriteLine("The solutions are:");
for (int i = 0; i < N; i++)
{
int x = solutions[i].Item1;
int y = solutions[i].Item2;
Console.WriteLine("Solution #" + (i + 1) + " is <" + x + "," + y + ">");
}
}
Console.ReadLine();
}
}
}
using System;
using System.Collections.Generic;
// en.wikipedia.org/wiki/Taxicab_number
// In mathematics, the N-th taxicab number, typically denoted Ta(n) or Taxicab(n),
// is defined as the smallest number that can be expressed as a sum of
// two positive algebraic cubes in 'N' distinct ways
namespace MathTrivia
{
class TaxicabNumber
{
static Tuple<int, int>[] solutions;
static bool Question(UInt64 A, UInt32 N)
{
// Step 1. Calculate 'max' as the largest value that when cubed is less than A
// And 'halfmax' as the largest value that when cubes is less than (A/2)
int max = 0;
int halfmax = 0;
{
UInt64 halfA = A / 2;
UInt64 t;
do
{
max++; // Test the next integer
t = (UInt64)max;
t = t * t * t;
if (t < halfA)
halfmax = max;
} while (t < A);
max--; // backup by one since last cube was too large
}
// Step 2. Precompute the cubes that we will need.
// Allocate and initialize an array of all cubes for 0..max
// Allocate a Map that given a UInt64 returns the cube root if one exists.
// The Map only needs to contain the cubes that are greater or equal to A/2
UInt64[] cubes = new UInt64[halfmax+1];
Dictionary<UInt64,int> roots = new Dictionary<UInt64,int>(max-halfmax+1);
for (int i = 0; i <= max; i++)
{
UInt64 t = (UInt64)i;
t = t * t * t;
// Add t to the cubes[] or the roots Map, or both when i == halfmax
if (i <= halfmax)
{
cubes[i] = t;
}
if (i >= halfmax)
{
roots.Add(t, i);
}
}
// Step 3. Search the range of integers that could satify the equation x^3 + y^3 == A
//
UInt64 numSolutions = 0;
for (int x = 0; x <= halfmax; x++)
{
UInt64 x3 = cubes[x];
UInt64 remaining = A - x3;
int y;
if (roots.TryGetValue(remaining, out y))
{
// the pair <x,y> satisfies the equation.
if (solutions == null)
{
solutions = new Tuple<int, int>[N];
}
solutions[numSolutions] = new Tuple<int, int>(x, y);
numSolutions++;
if (numSolutions >= N)
return true;
}
}
// We only found 'numSolutions', we didn't reach N
return false;
}
static void Main(string[] args)
{
UInt64 A;
UInt32 N;
if (args.Length == 0)
{
A = 48988659276962496;
N = 5;
Console.WriteLine("Sample example, let A=" + A + " and N=" + N);
}
else
{
if (args.Length != 2)
{
Console.WriteLine("Usage: Program A, N");
}
if (UInt64.TryParse(args[0], out A))
{
Console.WriteLine("Usage: Program >>A<<, N");
}
if (UInt32.TryParse(args[1], out N))
{
Console.WriteLine("Usage: Program A, >>N<<");
}
}
bool result = Question(A, N);
Console.WriteLine("Question(A is " + A + ", N is " + N + ") is " + result);
if (result)
{
Console.WriteLine("The solutions are:");
for (int i = 0; i < N; i++)
{
int x = solutions[i].Item1;
int y = solutions[i].Item2;
Console.WriteLine("Solution #" + (i+1) + " is <" +x+ "," +y+ ">");
}
}
Console.ReadLine();
}
}
}
Here is a C# solution:
using System;
using System.Collections.Generic;
// en.wikipedia.org/wiki/Taxicab_number
// In mathematics, the N-th taxicab number, typically denoted Ta(n) or Taxicab(n),
// is defined as the smallest number that can be expressed as a sum of
// two positive algebraic cubes in 'N' distinct ways
namespace MathTrivia
{
class TaxicabNumber
{
static Tuple<int, int>[] solutions;
static bool Question(UInt64 A, UInt32 N)
{
// Step 1. Calculate 'max' as the largest value that when cubed is less than A
// And 'halfmax' as the largest value that when cubes is less than (A/2)
int max = 0;
int halfmax = 0;
{
UInt64 halfA = A / 2;
UInt64 t;
do
{
max++; // Test the next integer
t = (UInt64)max;
t = t * t * t;
if (t < halfA)
halfmax = max;
} while (t < A);
max--; // backup by one since last cube was too large
}
// Step 2. Precompute the cubes that we will need.
// Allocate and initialize an array of all cubes for 0..max
// Allocate a Map that given a UInt64 returns the cube root if one exists.
// The Map only needs to contain the cubes that are greater or equal to A/2
UInt64[] cubes = new UInt64[halfmax+1];
Dictionary<UInt64,int> roots = new Dictionary<UInt64,int>(max-halfmax+1);
for (int i = 0; i <= max; i++)
{
UInt64 t = (UInt64)i;
t = t * t * t;
// Add t to the cubes[] or the roots Map, or both when i == halfmax
if (i <= halfmax)
{
cubes[i] = t;
}
if (i >= halfmax)
{
roots.Add(t, i);
}
}
// Step 3. Search the range of integers that could satify the equation x^3 + y^3 == A
//
UInt64 numSolutions = 0;
for (int x = 0; x <= halfmax; x++)
{
UInt64 x3 = cubes[x];
UInt64 remaining = A - x3;
int y;
if (roots.TryGetValue(remaining, out y))
{
// the pair <x,y> satisfies the equation.
if (solutions == null)
{
solutions = new Tuple<int, int>[N];
}
solutions[numSolutions] = new Tuple<int, int>(x, y);
numSolutions++;
if (numSolutions >= N)
return true;
}
}
// We only found 'numSolutions', we didn't reach N
return false;
}
static void Main(string[] args)
{
UInt64 A;
UInt32 N;
if (args.Length == 0)
{
A = 48988659276962496;
N = 5;
Console.WriteLine("Sample example, let A=" + A + " and N=" + N);
}
else
{
if (args.Length != 2)
{
Console.WriteLine("Usage: Program A, N");
}
if (UInt64.TryParse(args[0], out A))
{
Console.WriteLine("Usage: Program >>A<<, N");
}
if (UInt32.TryParse(args[1], out N))
{
Console.WriteLine("Usage: Program A, >>N<<");
}
}
bool result = Question(A, N);
Console.WriteLine("Question(A is " + A + ", N is " + N + ") is " + result);
if (result)
{
Console.WriteLine("The solutions are:");
for (int i = 0; i < N; i++)
{
int x = solutions[i].Item1;
int y = solutions[i].Item2;
Console.WriteLine("Solution #" + (i+1) + " is <" +x+ "," +y+ ">");
}
}
Console.ReadLine();
}
}
}
step 1 : cube all the numbers in x and y remove all the elements > A or do not consider them in further steps
2. sort the cubed arrays
3. start from min of x and loop till the end of x
4. for every element in x take the elements from maximum of y (decreasing order) and check it it equals to A, do it for elements in y untill the result becomes less than A.
store all the values which equals A.
the above solution might require tweakings based on space constraints or any other conditions.
bool cupfun(unsigned int A, unsigned int n )
{
int count = 0;
int x=0, y=0;
while ( x*x*x < A) x++;
while (y <= x)
{
int cube = x*x*x + y*y*y;
if (cube > A) x--;
else if (cube < A) y++;
else
{
cout << "pair:" << x << " " << y << " pair:" << y << " " << x << endl;
x--; y++;
count+=2;
}
}
return (count == n);
}
Simplest solution
------------------------
bool npairs(int A, int N) {
int count = 0;
for(int i = 1; i < A; i++)
for(int j = i; j < A; j++)
if(A % (i + j) && A %(i*i + j*j - i*j))
count++;
if(count >= N)
return true;
return false;
}
bool npairs(int A, int N) {
int count = 0;
for(int i = 1; i < A; i++)
for(int j = i; j < A; j++)
if((A % (i + j) == 0)&& (A % (i*i + j*j - i*j) == 0))
count++;
return (count >= N);
}
Simple solution which takes O(cuberoot(A)) space and similar time. Precompute the cubes and then do one pass to find out how many pairs add to A.
bool IsPresent(UINT A, UINT N)
{
vector<UINT> cubes;
for (UINT i=1; i < A; i++)
{
UINT cube = i*i*i;
if (cube < A)
{
cubes.push_back(cube);
}
else
{
break;
}
}
UINT min=0, max = cubes.size() -1, count=0;
while ( (min < max) && (count < N))
{
if (cubes[min] + cubes[max] < A)
{
min++;
}
else if (cubes[min] + cubes[max]== A)
{
count ++;
min++;
max--;
}
else
{
max--;
}
}
return (count ==N);
}
Can you please provide an Example?
- JSDUDE April 22, 2013If you are taking x and y as input then there is only one value for (x^3 + y^3).
May be I am missing something here.