Adobe Interview Question
Member Technical StaffsCountry: India
Interview Type: In-Person
O(n) solution using a set
#include <iostream>
#include <set>
#include <cmath>
int main() {
int N = 91;
std::set<long> cubics_set;
// Generating all cubic values between 1 and N
for(int i = 1; i < N; i++) {
cubics_set.insert(std::pow(i, 3));
}
for(auto it = cubics_set.begin(); it != cubics_set.end(); ++it) {
if(*it > N)
break;
long required = N - *it;
if(cubics_set.find(required) != cubics_set.end())
std::cout << "a:" << *it << " "
<< "b:" << required << std::endl;
}
return 0;
}
The Solution is O(n) -- Still can be reduced
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
public class cubeN {
public static void main(String[] args) {
int sum = 0,l = 1;
HashMap<Integer,Integer> hm = new HashMap<Integer,Integer>();
System.out.println("Enter the Value of N :");
Scanner s = new Scanner(System.in);
int n = s.nextInt();
for(int j = 0; j < n; j++){
sum = j*j*j;
hm.put(sum,j);
}
Set set = hm.entrySet();
Iterator i = set.iterator();
while(i.hasNext()){
Map.Entry me = (Map.Entry)i.next();
int Value = n - (Integer) me.getKey();
int num1 = (Integer)me.getValue();
if(hm.containsKey(Value)){
int num2 = hm.get(Value);
System.out.println("Combination -"+l+" "+num1+","+num2);
l++;
}
}
}
}
solution in python
import math
def find_sol(a, b, N):
# solution
if (pow(a, 3) + pow(b, 3) == N):
return 1
# over solution
elif (pow(a, 3) + pow(b, 3) > N):
return 0
# under solution
else:
return (find_sol(a + 1, b, N) + find_sol(a, b + 1, N)
if __name__ == '__main__':
N = 2 # or some other value
num_sol = find_sol(0,0,N)
num_sol/=2
Can we use binary search in this?
max value for this a^3 + b^3 will be N and mininum value will be 0.
I am sure the below code is not going to work for some cases but right now not able to figure out.
So search will be like this:
#include <math.h>
int power(int no, int power)
{
int sum = 1;int i;
for(i=0;i<power;i++) {
sum = sum*no;
}
return sum;
}
void bsearch(int low, int high, int no) {
printf("low %d high %d\n", low, high);
/* base cases */
if(low < 0 || high > no || high < 0 || low > no)
return;
if(power(low, 3) + power(high, 3) == no) {
printf("%d %d\n", low, high);
return;
} else if(power(low, 3) + power(high, 3) >= no) {
bsearch(low, high-1, no);
} else
bsearch(low+1, high, no);
}
int main()
{
bsearch(0, 9/2, 9);
}
Could be done in O(N^(1/3)) (cubic root).
for (int a = 0; a * a * a <= N; ++a) {
int b3 = N - a * a * a;
int b = (int)pow((double)b3, 1. / 3.); // That could be done manually with binary search or something else.
/* Here we can check close ints to be sure with precision errors */
bool is_cubic_root = false;
int mem = -1;
for (int delta = -2; delta <= 2; ++delta) if (pow3(b + delta) == b3) is_cubic_root = true, mem = b + delta;
if (is_cubic_root) {
cout << a << ' ' << mem << endl;
}
}
function findCubedPairs(n) { // assume n > 0
var powers = {};
var result = [];
for (var i = 0; i < n; i++) {
powers[i * i * i] = i;
}
for (var i = 0; i < n; i++) {
var a = i;
var aCubed = i*i*i;
var bCubed = n - aCubed;
var b;
var neg = 1;
if (bCubed < 0) {
neg = -1;
}
var b = powers[bCubed * neg];
if (powers[bCubed * neg]) {
if (neg === -1) {
result.push([a, -b]);
result.push([-a, b]);
} else {
result.push([a, b]);
}
}
}
return result;
}
void PrintAllCombination(int iNumber)
{
//To reduce the number of iterations.....
int iMaxLimit = pow((double)iNumber, (double)1/3.) + 0.5 ;
int iA, iB;
int iLoopCounter = 0;
int iFirstVal;
//If the cube of the value is equal to number then again we are adding some value in to it, that will be waste of iteration & time.
for( iA = 0; iA <= iMaxLimit; iA ++ )
{
//Calculating to reduce the multiplication process again & again.
iFirstVal = iA * iA * iA;
for( iB = 0; iB <= iMaxLimit; iB ++ )
{
if( iFirstVal + iB * iB * iB == iNumber )
printf("A := %d B := %d\n", iA, iB);
iLoopCounter ++;
}
}
printf("Total Iteration:%d", iLoopCounter);
}
Here is the optimized code that will take less time to compute the combination... please comment if I missed anything..
void PrintAllCombination(int iNumber)
{
//To reduce the number of iterations.....
int iMaxLimit = pow((double)iNumber, (double)1/3.) + 0.5 ;
int iA, iB;
int iLoopCounter = 0;
int iFirstVal;
//If the cube of the value is equal to number then again we are adding some value in to it, that will be waste of iteration & time.
for( iA = 0; iA <= iMaxLimit; iA ++ )
{
//Calculating to reduce the multiplication process again & again.
iFirstVal = iA * iA * iA;
for( iB = 0; iB <= iMaxLimit; iB ++ )
{
if( iFirstVal + iB * iB * iB == iNumber )
printf("A := %d B := %d\n", iA, iB);
iLoopCounter ++;
}
}
printf("Total Iteration:%d", iLoopCounter);
}
import static java.lang.System.exit;
import java.util.Scanner;
public class Number {
int a, b;
Number() {
a = 0;
b = 0;
}
public int[] findAB(int n) {
int sum = 0;
int i;
int j;
for (i = 0; i < 1000; i++) {
for (j = 0; j < 1000; j++) {
sum = i * i * i + j * j * j;
if(sum==n){
System.out.println(i+" , "+j);
}
}
}
return null;
}
public static void main(String args[]) {
int n;
Number num = new Number();
Scanner in = new Scanner(System.in);
n = in.nextInt();
num.findAB(n);
}
}
import static java.lang.System.exit;
import java.util.Scanner;
public class Number {
int a, b;
Number() {
a = 0;
b = 0;
}
public int[] findAB(int n) {
int sum = 0;
int i;
int j;
for (a = 0; a < 1000; a++) {
for (b = 0; b < 1000; b++) {
sum = a * a * a + b * b * b;
if(sum==n){
System.out.println(a+" , "+b);
}
}
}
return null;
}
public static void main(String args[]) {
int n;
Number num = new Number();
Scanner in = new Scanner(System.in);
n = in.nextInt();
num.findAB(n);
}
}
}
#include <stdio.h>
main()
{
int a,b,i,j,k=0;
printf("enter no.");
scanf("%d",&N);
for(a=0;a<N;a++)
{
if((a*a*a)>N)
{
a--;
break;
}
k++;
}
for(i=a;i>=0;i--)
{
for(j=0;j<=a;j++)
{
if(((i*i*i)+(j*j*j))==N)
printf("%d,%d\n",i,j);
if(((i*i*i)+(j*j*j))>N)
break;
}
k++;
}
printf("\nnumber of comparison %d\n",k);
}
O(n)
1. Find the cube of each number starting from 1 to (n-3) and store in an array.
2. Search the combination of numbers which can sum to n ( I used binary search to do so)
- Ricky January 31, 2014