Amazon Interview Question
Country: India
Hi,
Could someone explain me the significance of the variables used in the program...
int N=5; // what is N ?
int count=0; // What is count...?
void sumKN(int k, int n, int r) // and most chiefly on what is k,n,r..?
sumKN(1,6,3); // why is this 1, 6 ,3...? Where does this 6 came from...?
Slightly confusing for me and many Thanks in advance.
int n; // target
int ans = 0;
void get_cnt(int *a, int i, int sum, int num)
{
if (num == 0 && sum == n ) {ans++; return;}
if ( i < 0 || num < 0 || sum < 0 ) return;
get_cnt(a, i-1, sum-a[i], num-1);
get_cnt(a, i-1, sum, num);
}
To understand the solution more clearly, you can watch this wonderful video
youtu.be/B9C-UntuQ7c
I kind of burst into laugh. For those non-Chinese guys, the replier of this question's ID is "diaosi", which in Chinese internet means: un-redemptable loser, hahah, u r funny, dude.
Well, it is an appropriate name.
The question asks for number of ways, and diaosi enumerates them and maintains a count.
Consider a different question: How many even numbers are there, less than 2^64.
diaosi's solution is similar to enumerating all the even integers and adding one to the count!
public class KNumSumToN {
public static int count(int k, int[] numbers, int n) {
return count(k, numbers, numbers.length-1, n);
}
public static int count(int k, int[] numbers, int index, int n) {
if (k == 0 && n == 0 || (k == 1 && index == 0 && n - numbers[0] == 0)) {
return 1;
} else if (index <= 0 || k < 0 || n < 0) {
return 0;
} else {
return count(k - 1, numbers, index - 1, n - numbers[index - 1])
+ count(k, numbers, index - 1, n);
}
}
public static void main(String[] args) {
int[] arr1= new int[] { 3,1,2,2,0,4,0};
System.out.println(count(2, new int[] { 1, 1, 0 }, 3));
System.out.println(count(2,arr1, 4));
}
}
def sum_to_n(n):
count = 1
# Edge case.
if n == 1:
return 1
for k in range(2, n+1):
# Loop over the starting points.
for start in range(1, n - k + 1):
# This ending point will leave out the last value.
end = start + k - 1
# If there are trailing values, then permute them.
for value in range(end, n+1):
# Check for success.
if n == sum(range(start, end) + [value]):
count += 1
return count
print sum_to_n(5)
Another solution -
It is redundant to pass in an array from 1-n, so the main function f() just takes n and k.
void f(int n, int k)
{
int *a = new int[k]; // for print the combinations
f1(n, k, 1, a, 0)
}
void f1(int n, int k, int min, int* buf, int cur)
{
if(n==0 && k==0)
{
print(buf, cur); // print the combination from 0 to cur.
return;
}
if(k>0)
{
for(int i=min; i<n+1;++i)
{
buf[cur]=i;
f1(n-i, k-1, i+1, buf, cur+1);
}
}
}
#include <stdio.h>
int findCount(int n,int k)
{
int count=0,sum=0;
int i=1;
int sumk=k*(k-1)/2;
while(i <= n/2)
{
sum=(i*k)+sumk;
if(sum < n)
{
if(n-sum+(i+k-1)<n)
count=count+k;
}
else
break;
i++;
}
return count;
}
int main()
{
int n,k;
scanf("%d",&n);
scanf("%d",&k);
int count=findCount(n,k);
printf("Count = %d\n",count);
return 0;
}
void F(int Last, int CurrSum, int N, int Expect, int &Count, int CurrLevel, int K)
{
if(CurrSum == Expect && K == CurrLevel)
{
++Count;
}
else if(CurrSum < Expect && CurrLevel < K)
{
for(int i = Last; i < N; ++i)
{
F(i, CurrSum + i, N, Expect, Count, CurrLevel + 1, K);
}
}
}
void Entry(int N, int K)
{
int Count = 0;
F(0, 0, N, N, Count, 0, K);
}
consider n=5, then no. of ways to select nos. from 1 to 5 are
{5},{4,1},{3,2} => no. of ways=3.
similarly for n=10
{10},{9,1},{8,2},{7,3},{7,2,1},{6,4},{6,3,1},{5,3,2},{5,4,1} => no. of ways=9
similarly for n=11,
{11},{10,1},{9,2},{8,3},{8,2,1},{7,4},{7,3,1},{6,5},{6,3,2},{6,4,1},{5,4,2},{5,3,2,1} => no. of ways=12.
Note- no number between 1 to n must be repeated
source code-
#include<stdio.h>
int ways(int n)
{
int wayn=0;
if(n<3)return 1;
int i;
int way[n+1];
way[1]=1;
way[2]=1;
for(i=1;i<=(n+1)/2;i++)
{
wayn+=ways(i);
}
if(n%2&& n>=5)
way[n]=wayn-1;
else
way[n]=wayn;
return way[n];
}
int main()
{
int n;
scanf("%d",&n);
printf("%d\n",ways(n));
getch();
return 0;
}
{
#include <iostream>
#include <stdio.h>
bool checkForSum(int k, int n, int size, int* A, int start)
{
if(k == 0 && n == 0)
return true;
if(k == 0 && n > 0)
return false;
if(n < 0 )
return false;
if(start >= size)
return false;
printf("\n n %d k %d start %d A[start] %d \n", n, k, start, A[start]);
if(checkForSum(k-1, n- A[start], size, A, start +1))
{
printf("\n %d \n", A[start] );
return true;
}
else
{
return checkForSum(k,n, size, A, start+1);
}
}
int main()
{
int A[5] = {4, 1, 2, 0, 1};
checkForSum(3, 4, 5, A, 0 );
return 1;
}
}
// Another simple code :
#include<iostream>
using namespace std;
int c=0,n;
int sum_set(int sum,int i,int k)
{ if(i>n+1) return 0;
if(k<0) return 0;
if(k==0)
{ if(sum==0) { c++; return 0; }
else return 0;
}
sum_set(sum-i,i+1,k-1);
sum_set(sum,i+1,k);
}
main()
{ int k;
scanf("%d %d",&n,&k);
sum_set(n,1,k);
printf("%d\n",c);
system("pause");
return 0;
}
Exhaustive backtracking approach:
void foo(int* arr,int k,int* res,int depth,int N,int sum,int dec)
{
int i;
if(sum>N) return;
if(depth==k)
{
if(sum==N)
print(res,N);
}
else
{
if(dec<N)
{
if(!res[dec])
{
res[dec]=1;
foo(arr,k,res,depth+1,N,sum+arr[dec],dec+1);
res[dec]=0;
foo(arr,k,res,depth,N,sum,dec+1);
}
}
}
}
Complete code here: ideone.com/BeAnJ
This code is running fine, I have kept the printf intact as it helped me in finding solution
- Anonymous July 13, 2012