Accenture Interview Question
Software AnalystsCountry: India
Interview Type: In-Person
void printVec(vector<int> sol, vector<char> sign)
{
for(int i = 0; i <sol.size(); i++)
{
cout <<sign[i]<<sol[i];
}
}
void PrintCombination(vector<int> numbers, vector<int> sol, vector<char> sign, int target1, int pos)
{
if(target1 == 0 )
{
cout << endl << "-------------Solution-------------"<<endl;
printVec(sol, sign);
cout << endl << "-------------Solution-------------"<<endl;
return;
}
for(int i = pos; i<numbers.size(); i++)
{
int temp1 = target1-numbers[i];
sol.push_back(numbers[i]);
sign.push_back('+');
PrintCombination(numbers, sol, sign, temp1, i+1);
//sol.pop_back();
//sol.push_back(numbers[i]);
sign.pop_back();
sign.push_back('-');
temp1 = target1+numbers[i];
PrintCombination(numbers, sol, sign, temp1, i+1);
sign.pop_back();
sol.pop_back();
}
}
int main()
{
vector<int> numbers;
vector<int> solu;
vector<char> sign;
numbers.push_back(1);
numbers.push_back(2);
numbers.push_back(3);
numbers.push_back(4);
numbers.push_back(5);
PrintCombination(numbers, solu, sign, 3, 0);
return 0;
}
#include<iostream>
#include<malloc.h>
#include<string.h>
using namespace std;
int flag =0;
void calculation(int *a,char *s,int n)
{
int i,output=a[0];
for(i=0; i< n-2 ;i++){
if(s[i]=='+') {
output +=a[i+1];
}
else output-=a[i+1];
}
if(output == a[n-1]){
flag = 1;
for(i=0; i<n-2 ;i++){
cout<<a[i]<<s[i];
}
cout<<a[i]<<" = "<<a[i+1]<<endl;
}
}
void swap (char *x, char *y)
{
char temp;
temp = *x;
*x = *y;
*y = temp;
}
void prm(int *a , int n, char *s, int begin, int end)
{
int j;
char was[256];
bzero(was, 256);
if (begin == end){
//cout<<s<<endl;
calculation(a,s,n);
}
else
{
for (j = begin; j <= end; j++)
{
if (!was[*(s+j)]) {
swap((s+begin), (s+j));
prm(a,n,s, begin+1, end);
swap((s+begin), (s+j));
was[*(s+j)] = 1;
}
}
}
}
void pnc (int *a, int n)
{
int i;
char *s=new char[n-2];
for(i=0;i<n-2;i++) s[i] = '+';
//cout<<s<<endl;
calculation(a,s,n);
for(i=0;i<n-2;i++){
s[i]= '-';
//cout<<"s before prm = "<<s<<endl;
prm(a,n,s,0,n-3);
}
}
main()
{
int n;
cout<<"Enter number of elements\n";
cin >>n;
int *a=new int[n];
cout<<"Enter set\n";
for(int i=0;i<n;i++) cin>> a[i];
cout<<"\n";
pnc(a,n);
if(flag ==0 ) cout<<"No solution\n";
}
class Test{
static int count=0;
public static void main(String args[]){
System.out.println("Enter digits");
Scanner scanner=new Scanner(System.in);
String numbers[]=scanner.nextLine().split(" ");
System.out.println("Enter answer which is wanted");
int ans=scanner.nextInt();
if(numbers.length==1&&Integer.parseInt(numbers[0])==ans){
System.out.println("The solution is:"+numbers[0]);
return;
}
generateAllEquations(numbers,ans,numbers[0],1);
if(count==0)
System.out.println("No solution");
}
private static void generateAllEquations(String[] numbers, int ans,String string, int index) {
if(index==numbers.length){
if(checkAns(string,ans))
System.out.println("The "+(++count)+": solution is:"+string);
return;
}
generateAllEquations(numbers,ans,string+"+"+numbers[index],index+1);
generateAllEquations(numbers,ans,string+"-"+numbers[index],index+1);
}
private static boolean checkAns(String str,int ans){
String temp="";
int result=0;
char prev=' ';
for(int l=0;l<str.length();l++){
if(str.charAt(l)=='+'||str.charAt(l)=='-'){
if(prev=='+')
result=result+Integer.parseInt(temp);
else if(prev=='-')
result=result-Integer.parseInt(temp);
else
result=Integer.parseInt(temp);
prev=str.charAt(l);
temp="";
}
else
temp+=str.charAt(l);
}
if(prev=='+')
result=result+Integer.parseInt(temp);
else if(prev=='-')
result=result-Integer.parseInt(temp);
if(result==ans)
return true;
return false;
}
}
The complexity is n2.
We can solve this problem using backtracking, here is the code, basically we try all the possible +- assignments
YOu can understand this solution by watching this video
- coolsolution September 09, 2012youtube.com/watch?v=14Jb7aycv3c