Epic Systems Interview Question Software Engineer / Developers
but what about 17521, I think it cannot solve the problem when the original order need to be changed.
Yes, as wei said, this will not work for a different combination. I think we have to find all permutation of the digits first and use this check function for each permutation.
Anyway Gayathiri's check function is excellent. I tried it with permutation and found all correctly printed.
Any further solutions?
I think in this problem two things that are evident are
1. The number formation will be always of consecutive numbers like 12 + 5 and not like 15 + 2 for case of 17512 so
2. if we have to take just a single + then there will always be a split of three number
other wise this will become something of N! where N will be single digit.
If there are only one + and = then the algorithm will have
int [] split(x) {
int number[n][3];
split and add the number to array according to consecutive digits.
}
checksum() {
checksum between three number of they form the equation.
}
Just the simplest idea that i thought of but not a complete solution.
Please do post comment
you have one = and one +. You have to place them inside the number such that the resulting equation is true.
We can have some simpler one.
lets have one example.
"25631"
Equation can be: 25+6=31.
follow the below steps
1) 2+5=631 (no 7 != 631 also 7<631)
2) 2+56=31 (no 58 !=31 also 58>31, break the loop here itself)
3) Now instead of 2 take 25 and start again.
25+6=31 (yes 31==31, break the loop again).
Above steps can be converted into code.
package string.questions;
public class PlusnEqual {
String number;
PlusnEqual(String number){
this.number = number;
}
public static void main(String[] args){
char[] input = new String("1123").toCharArray();
System.out.println("it failed "+ checkSum(input));
}
public static boolean checkSum(char[] inputNumber){
boolean status = false;
int seperator1 = 0;
int seperator2 = 0;
int number1;
int number2;
int resultNum;
boolean leftRight = false;
for(int i=inputNumber.length-1;i>=0;i--){
for(int j=0;j<=inputNumber.length-1;j++){
System.out.println("---Combination cases :: i = "+ i+ " j = " + j );
if(i!=j && Math.abs(i-j)!=1 ){
System.out.println("Considering cases :: i = "+ i+ " j = " + j );
if(j<i){
seperator1 = (int) Math.floor(j);
seperator2 = (int) Math.floor(i);
}else{
seperator1 = (int) Math.floor(i);;
seperator2 = (int) Math.floor(j);;
}
System.out.println("seperator1 == "+seperator1 + "seperator2 == "+seperator2 );
String num1 = "";
String num2 = "";
String result = "";
for(int num1_i=0;num1_i<=seperator1;num1_i++){
num1 = num1 + inputNumber[num1_i];
}
for(int num2_i=seperator1+1;num2_i<seperator2;num2_i++){
num2 = num2 + inputNumber[num2_i];
}
for(int res_i=seperator2;res_i<inputNumber.length;res_i++){
result = result + inputNumber[res_i];
}
System.out.println("num1 == "+num1+ "num2 == "+num2+" result == "+result);
// if(num1.length()==0 || num2.length()==0 || result.length()==0 ){
// continue;
// }
if(j<i){
number1 = Integer.parseInt(num1);
number2 = Integer.parseInt(num2);
resultNum = Integer.parseInt(result);
}else{
resultNum = Integer.parseInt(num1);
number2 = Integer.parseInt(num2);
number1 = Integer.parseInt(result);
}
System.out.println("Considering cases :: " + number1+"+"+number2+"="+resultNum);
if(resultNum == (number1 + number2) ) {
System.out.println("Final Answer is :: "+number1+"+"+number2+"="+resultNum);
return true;
}
}
}
}
return status;
}
}
The messages in the above code are not very clear
if the function returns:: true
that means + and = can be used to produce the required combination and the message with final answer returns that
combination.
if it returns false then there does not exists such a combination and messages are just the combinations that were checked.
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
using namespace std;
class PlusEqual{
private:
vector<string> a,b,c;
string digits;
int A,B,C;
stringstream buff;
public:
PlusEqual(string str){
digits=str;
parse();
}
void parse(){
for(unsigned int i=1;i<digits.length();i++){
for(unsigned int j=1;j<digits.length()-i;j++){
a.push_back(digits.substr(0,i));
b.push_back(digits.substr(i,j));
c.push_back(digits.substr((i+j),digits.length()));
}
}
}
void printRelation(){
for(unsigned int i=0;i<a.size();i++){
buff.clear();
buff<<a.at(i);
buff>>A;
buff.clear();
buff<<b.at(i);
buff>>B;
buff.clear();
buff<<c.at(i);
buff>>C;
if(A==B+C)
cout<<A<<"="<<B<<"+"<<C<<endl;
if(B==A+C)
cout<<B<<"="<<A<<"+"<<C<<endl;
if(C==B+A)
cout<<C<<"="<<A<<"+"<<B<<endl;
}
}
};
int main()
{
PlusEqual pe1("25631");
pe1.printRelation();
char a; cin>>a;
return 0;
}
import java.util.*;
import java.io.*;
class ifsum
{
public static void main(String[] args) throws IOException
{
ifsum obj = new ifsum();
System.out.println("Enter the number");
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String input = br.readLine();
ArrayList curlist = new ArrayList();
System.out.println(obj.recurse(curlist,input));
}
public Boolean recurse(ArrayList curlist, String input)
{
String split_left="";
String split_right = "";
for(int i=0;i<input.length();i++)
{
split_left = split_left+input.charAt(i);
System.out.println("left: " + split_left);
split_right = input.substring(i+1);
System.out.println("right: " + split_right);
if(curlist.size()==0)
{
ArrayList nums = new ArrayList();
nums.add(Integer.parseInt(split_left));
nums.add(Integer.parseInt(split_right));
if(check(nums))
return true;
}
else
{
ArrayList nums = new ArrayList();
for(int j=0;j<curlist.size();j++)
{
nums.add(curlist.get(j));
}
nums.add(Integer.parseInt(split_left));
if(split_right.length()>0)
nums.add(Integer.parseInt(split_right));
if(check(nums)==true)
return true;
}
if(split_left.length()>0)
curlist.add(Integer.parseInt(split_left));
if(recurse(curlist,split_right)==true)
return true;
curlist.remove(curlist.size()-1);
}
return false;
}
public Boolean check(ArrayList nums)
{
for(int i=0;i<nums.size();i++)
{
int sum =0;
for(int j=0;j<nums.size();j++)
{
if(i==j)
continue;
int temp = (Integer)nums.get(j);
sum = sum + temp;
int temp1= (Integer)nums.get(i);
if(sum==temp1)
{
return true;
}
}
}
return false;
}
}
allen7126's idea is good.
for all permutations code is :-
//permutation of a string
void DoPermutation(const string& s, string& CurrStr, int CurrPos, vector<bool> Used)
{
//if reach the last postion, print current char and return
if (CurrPos == s.size())
{
cout<<CurrStr<<endl;
}
else // else loop through all chars
{
for (unsigned int i = 0; i < s.size(); ++i)
{
// if used, continue
if (Used[i]) continue;
// if not, output the current char, set it as used
CurrStr[CurrPos] = s[i];
Used[i] = true;
//do permutation from the next position
DoPermutation(s,CurrStr, CurrPos+1,Used);
//set the current char as unusd
Used[i] = false;
}
}
}
void StrPerm(const string S)
{
vector<bool> Used(S.size(),false);
string str(S.size(),' ');
DoPermutation(S, str, 0, Used);
'''Given a number find whether the digits in the number can be used to form an equation with + and '='. That is if the number is 123, we can have a equation of 1+2=3. But even the number 17512 also forms the equation 12+5=17.'''
def form_equation(number):
def check_num(num1, num2, num3):
if int(num1) + int(num2) == int(num3):
print '%s + %s = %s' %(num1, num2, num3)
elif int(num1) + int(num3) == int(num2):
print '%s + %s = %s' %(num1, num3, num2)
elif int(num2) + int(num3) == int(num1):
print '%s + %s = %s' %(num2, num3, num1)
def generate_combinations(number):
res = []
number = str(number)
n = len(number) / 2 # because the right side of the equation should always have more digits than the left
for i in range(n): # left side
m = i + 1
for j in range(m, len(number)-1): # right side
num1 = number[0:m]
num2 = number[m:j+1]
num3 = number[j+1:len(number)]
check_num(num1, num2, num3)
if number < 100:
raise Exception("Error. Please give at least a 3-digit number.")
combinations = generate_combinations(number)
# form_equation(1) # error
form_equation(1234567)
form_equation(17512)
form_equation(25631)
<pre lang="" line="1" title="CodeMonkey35709" class="run-this">/* The class name doesn't have to be Main, as long as the class is not public. */
class Main
{
public static void main (String[] args) throws java.lang.Exception
{
java.io.BufferedReader r = new java.io.BufferedReader (new java.io.InputStreamReader (System.in));
String s;
while (!(s=r.readLine()).startsWith("42"))
{
System.out.println(InnerSum.splitPermutations(s));
}
}
}
class InnerSum {
static boolean checkSum (int n1, int n2, int n3)
{
if(n1 == (n2 + n3))
return true;
else
if(n2 == (n1 + n3))
return true;
else
if(n3 == (n1 + n2))
return true;
else
return false;
}
static boolean splitPermutations (String num)
{
int len = num.length();
for (int i = 1; i < (len - 1); i++)
{
for(int j = (i + 1); j < len; j++)
{
if(checkSum(Integer.parseInt(num.substring(0,i)), Integer.parseInt(num.substring(i,j)), Integer.parseInt(num.substring(j,len))))
return true;
}
}
return false;
}
}
</pre><pre title="CodeMonkey35709" input="yes">123
124
12517
</pre>
/* program to find if the digits in a numbe forma sequence such
that sum is equal to last one
eg 12121236 === 12 + 12 + 12 = 36
*/
#include<stdio.h>
#include<stdlib.h>
char number[100] = {'\0'};
int length = 0;
int form_number(int from, int to){ //not including 'to'
int num = 0;
int i = 0;
for(i= from;i<to;i++){
num = (num*10) + (number[i]-48);
}
return num;
}
void reverse(char number[]){
int i = 0;
char tmp = '0';
while(i<length/2){
tmp = number[i];
number[i] = number[length-1-i];
number[length-i-1] = tmp;
i++;
}
}
// check if the prev sum(n1) + new number = next contiguos numbers. if so, print,else, recuresivly call over the
// left over string.
// for loop makes sure.all sizes of number are taken into account in current iteration
void check(int n1, int last){ // last points to the the point from where to start in current iteration
int n2=0,n3=0;
int i,j,k;
for(i=last+1;i<length;i++){
n2 = form_number(last,i);
n3 = form_number(i,length);
if(n1 + n2 == n3){
printf("\n found the number:%s",number);
break;
}
else{
// printf(" --%d ",n2);
check(n1+n2, i); // recuresivly call for furthur permutations.
}
}
}
void main(){
int i, j,k,l=0 ;
printf("\n enter a number :");
scanf("%d", &i);
printf("\n Enter the last number in the range ");
scanf("%d", &j);
while(i!=j){
length = 0;
for(k=0;k<100;k++)
number[k] = '\0';
l = 0;
k = i;
while(k!=0){
length++;
number[l++] = (k%10)+48;
k = k/10;
}
//reverse the string formed
reverse(number);
//start from LSB,towards MSB for parsing
//printf("\n Checking %s ",number);
check(0,0);
i++;
}
}
public class equationStr {
public static void main(String[] args) {
String str="11314";
for(int i=1;i<str.length()-1;i++){
for(int j=i+1;j<str.length();j++){
String part1=str.substring(0, i);
String part2=str.substring(i, j);
String sum=str.substring(j, str.length());
int p1=Integer.parseInt(part1);
int p2=Integer.parseInt(part2);
int s=Integer.parseInt(sum);
if(p1+p2==s){
System.out.println("yes baz: "+p1+"+"+p2+"="+s);break;
}
}
}
}
}
package com;
import java.util.ArrayList;
public class SumNumbers {
public static void main(String[] args) {
findSumNumbers("17521");
}
private static void findSumNumbers(String string) {
if (string.length()<3) return;
char[] arr = string.toCharArray();
ArrayList<Node> res = basic(arr);
if(string.length()>3){
for(int i=3;i<arr.length;i++){
res = update(res,arr[i]);
}
}
for(Node I:res){
//System.out.println(I.str[0]+" + " + I.str[1] +" = "+I.str[2]);
if((Integer.parseInt(I.str[0])+Integer.parseInt(I.str[1]))==Integer.parseInt(I.str[2])){
System.out.println("Sucess " + I.str[0]+" + " + I.str[1] +" = "+I.str[2]);
}
}
}
private static ArrayList<Node> update(ArrayList<Node> res, char c) {
ArrayList<Node> update = new ArrayList<>();
for(Node node:res){
for(int j=0;j<node.str.length;j++){
for(int i=0;i<node.str[j].length()+1;i++){
Node temp = new Node();
temp.str[0]=node.str[0];temp.str[1]=node.str[1];temp.str[2]=node.str[2];
temp.str[j]=node.str[j].substring(0,i)+c+node.str[j].substring(i,node.str[j].length());
update.add(temp);
}
}
}
System.out.println(update.size()+" "+c);
return update;
}
private static ArrayList<Node> basic(char[] arr) {
ArrayList<Node> bas = new ArrayList<>();
for(int i=0;i<3;i++){
Node temp = new Node();
for(int j=0;j<3;j++){
int k =(j+i)%3;
temp.str[j]=arr[k]+"";
}
bas.add(temp);
}
System.out.println(bas.size());
return bas;
}
}
Here is working code in C++. Though the code might get a little more efficient with a little check on the boundary conditions I think the solution is so far good.
#include <cstdio>
#include <iostream>
#include <math.h>
using namespace std;
int func(long num);
int func(long num)
{
long int num1, n1, flag=0, n2, n3, i, j, dig, ct=0;
dig=num;
while (dig!=0)
{
dig/=10;
ct++;
}
for (i=ct-1; i>=2; i--)
{
n1=num/pow(10, i);
num1=fmod(num, pow(10, i));
for (j=i-1; j>=1; j--)
{
n2=num1/pow(10, j);
n3=fmod(num1, pow(10, j));
if (n1+n2==n3)
{
cout<<num<<endl;
cout<<n1<<"+"<<n2<<"="<<n3<<endl;
flag=1;
break;
}
else if (n3+n2==n1)
{
cout<<num<<endl;
cout<<n3<<"+"<<n2<<"="<<n1<<endl;
flag=1;
break;
}
else if (n1+n3==n2)
{
cout<<num<<endl;
cout<<n1<<"+"<<n3<<"="<<n2<<endl;
flag=1;
break;
}
}
if (flag==1)
{
break;
}
}
return 0;
}
int main()
{
long int x;
cin>>x;
func(x);
return 0;
}
static boolean canFormEquation(String input) {
if (input.length() < 3)
return false;
for (int i = 1; i < input.length() - 2; i++) {
for (int j = i + 1; j < input.length() - 1; j++) {
String n1 = input.substring(0, i);
String n2 = input.substring(i, j);
String n3 = input.substring(j, input.length());
ArrayList<String> pn1 = getPerm(n1);
ArrayList<String> pn2 = getPerm(n2);
ArrayList<String> pn3 = getPerm(n3);
for (int o = 0; o < pn1.size(); o++) {
for (int p = 0; p < pn2.size(); p++) {
for (int q = 0; q < pn3.size(); q++) {
int num1 = Integer.parseInt(pn1.get(o));
int num2 = Integer.parseInt(pn2.get(p));
int num3 = Integer.parseInt(pn3.get(q));
if (check(num1, num2, num3)) {
System.out.println("" + num1 + "," + num2 + ","
+ num3);
return true;
}
}
}
}
}
}
return false;
}
static boolean check(int n1, int n2, int n3) {
if (n1 + n2 == n3)
return true;
if (n2 + n3 == n1)
return true;
if (n1 + n3 == n2)
return true;
return false;
}
static ArrayList<String> getPerm(String num) {
ArrayList<String> result = new ArrayList<String>();
if (num.length() == 0) {
return result;
}
char first = num.charAt(0);
ArrayList<String> sub = getPerm(num.substring(1));
if (sub.size() != 0) {
for (int i = 0; i < sub.size(); i++) {
for (int j = 0; j <= sub.get(i).length(); j++) {
result.add(insertChar(sub.get(i), j, first));
}
}
} else {
result.add("" + first);
}
return result;
}
static String insertChar(String str, int index, char c) {
if (index == str.length()) {
return str + c;
}
return str.substring(0, index) + c + str.substring(index);
}
import java.util.ArrayList;
import java.util.List;
/**
* 1. We can use only one of each + and = operator. <br/>
* 2. Hence we need to extract 3 numbers out of the input string and test the
* equation.<br/>
* 3. Extracting three numbers from input string is tricky part. <br/>
* 3a. Each number can not exceed inputString.length()/2 in length. <br/>
* 3b. <br/>
* Extract n1 of size 1 to n. <br/>
* For each such n1, extract n2 from size 1 to n. <br/>
* n3 is always rest of the string. <br/>
* 4. Once you have n1,n2 and n3 and as we could move in any direction and use
* any combination of digits to for number, we need to compute all possible
* permutations of digits in each of n1, n2 and n3. If only moving forward was
* given, then we could have avoided permutation computation.<br/>
* 5. Pick each n1,n2 and n3 from the computed permutations of n1, n2 and n3 and
* check if the equation can be computed again in any of the three combinations
* as <br/>
* n1 + n2 == n3<br/>
* n1 + n3 == n2<br/>
* n2 + n3 == n1<br/>
* If anyone of above is true, we found the equation and exit.
*
*/
public class OnePlusEqualEquation {
public static void main(String[] args) {
String input = "14113";
canFormEquation(input);
}
private static void canFormEquation(String input) {
int limit = input.length() / 2;
for (int i = 0; i < limit; i++) {
for (int j = i + 1; j < limit + i + 1; j++) {
int num1 = Integer.parseInt(input.substring(0, i + 1));
int num2 = Integer.parseInt(input.substring(i + 1, j + 1));
int num3 = Integer.parseInt(input.substring(j + 1,
input.length()));
List<String> pn1 = getPerms(num1 + "");
List<String> pn2 = getPerms(num2 + "");
List<String> pn3 = getPerms(num3 + "");
for (int o = 0; o < pn1.size(); o++) {
for (int p = 0; p < pn2.size(); p++) {
for (int q = 0; q < pn3.size(); q++) {
int n1 = Integer.parseInt(pn1.get(o));
int n2 = Integer.parseInt(pn2.get(p));
int n3 = Integer.parseInt(pn3.get(q));
if (check(n1, n2, n3)) {
return;
}
}
}
}
}
}
}
private static boolean check(int num1, int num2, int num3) {
boolean result = false;
if (num1 + num2 == num3) {
System.out.println(num1 + "+" + num2 + "=" + num3);
result = true;
} else if (num1 + num3 == num2) {
System.out.println(num1 + "+" + num3 + "=" + num2);
result = true;
} else if (num2 + num3 == num1) {
System.out.println(num2 + "+" + num3 + "=" + num1);
result = true;
}
return result;
}
static List<String> getPerms(String input) {
List<String> permutations = new ArrayList<String>();
if (input == null) {
return null;
} else if (input.length() == 0) {
permutations.add("");
return permutations;
} else {
char first = input.charAt(0);
String remainder = input.substring(1, input.length());
List<String> words = getPerms(remainder);
for (String word : words) {
for (int k = 0; k <= word.length(); k++) {
permutations.add(insertCharAt(first, word, k));
}
}
return permutations;
}
}
private static String insertCharAt(char c, String word, int k) {
String start = word.substring(0, k);
String end = word.substring(k);
return start + c + end;
}
}
import java.util.ArrayList;
import java.util.List;
/**
* 0. Input string has to be of odd length and > 3. <br/>
* 1. We can use only one of each + and = operator. <br/>
* 2. Hence we need to extract 3 numbers out of the input string and test the
* equation.<br/>
* 3. Extracting three numbers from input string is tricky part. <br/>
* 3a. Each number can not exceed inputString.length()/2 in length. <br/>
* 3b. <br/>
* Extract n1 of size 1 to n. <br/>
* For each such n1, extract n2 from size 1 to n. <br/>
* n3 is always rest of the string. <br/>
* 4. Once you have n1,n2 and n3 and as we could move in any direction and use
* any combination of digits to for number, we need to compute all possible
* permutations of digits in each of n1, n2 and n3. If only moving forward was
* given, then we could have avoided permutation computation.<br/>
* 5. Pick each n1,n2 and n3 from the computed permutations of n1, n2 and n3 and
* check if the equation can be computed again in any of the three combinations
* as <br/>
* n1 + n2 == n3<br/>
* n1 + n3 == n2<br/>
* n2 + n3 == n1<br/>
* If anyone of above is true, we found the equation and exit.
*
*/
public class OnePlusEqualEquation {
public static void main(String[] args) {
// All tests .
// canFormEquation("12121236"); -> Does not work. 12+12+12=36. Uses +
// twice.
canFormEquation("12121236");
canFormEquation("1141");
canFormEquation("11413");
canFormEquation("14113");
canFormEquation("12315");
canFormEquation("123");
canFormEquation("31518");
canFormEquation("1234567");
canFormEquation("17512");
canFormEquation("25631");
}
private static void canFormEquation(String input) {
if (input.length() % 2 == 0 || input.length() <= 1) {
System.out.println("Invalid input string.");
return;
}
int limit = input.length() / 2;
for (int i = 0; i < limit; i++) {
for (int j = i + 1; j < limit + i + 1; j++) {
int num1 = Integer.parseInt(input.substring(0, i + 1));
int num2 = Integer.parseInt(input.substring(i + 1, j + 1));
int num3 = Integer.parseInt(input.substring(j + 1,
input.length()));
List<String> pn1 = getPerms(num1 + "");
List<String> pn2 = getPerms(num2 + "");
List<String> pn3 = getPerms(num3 + "");
for (int o = 0; o < pn1.size(); o++) {
for (int p = 0; p < pn2.size(); p++) {
for (int q = 0; q < pn3.size(); q++) {
int n1 = Integer.parseInt(pn1.get(o));
int n2 = Integer.parseInt(pn2.get(p));
int n3 = Integer.parseInt(pn3.get(q));
if (check(n1, n2, n3)) {
return;
}
}
}
}
}
}
}
private static boolean check(int num1, int num2, int num3) {
boolean result = false;
if (num1 + num2 == num3) {
System.out.println(num1 + "+" + num2 + "=" + num3);
result = true;
} else if (num1 + num3 == num2) {
System.out.println(num1 + "+" + num3 + "=" + num2);
result = true;
} else if (num2 + num3 == num1) {
System.out.println(num2 + "+" + num3 + "=" + num1);
result = true;
}
return result;
}
static List<String> getPerms(String input) {
List<String> permutations = new ArrayList<String>();
if (input == null) {
return null;
} else if (input.length() == 0) {
permutations.add("");
return permutations;
} else {
char first = input.charAt(0);
String remainder = input.substring(1, input.length());
List<String> words = getPerms(remainder);
for (String word : words) {
for (int k = 0; k <= word.length(); k++) {
permutations.add(insertCharAt(first, word, k));
}
}
return permutations;
}
}
private static String insertCharAt(char c, String word, int k) {
String start = word.substring(0, k);
String end = word.substring(k);
return start + c + end;
}
}
public class TryPlusEqual {
- Gayathiri November 13, 2010public static int count = 0;
public static int check(int n1,int n2,int n3)
{
count++;
if(n1+n2==n3)
{
System.out.println(n1+"+"+n2+"="+n3);
return 1;
}
else if(n2 + n3 == n1)
{
System.out.println(n2+"+"+n3+"="+n1);
return 2;
}
else if(n1+n3==n2)
{
System.out.println(n1+"+"+n3+"="+n2);
return 3;
}
else
return 0;
}
public static void main(String args[])
{
String f = "17512";
int n = f.length()/2;
System.out.println(n);
for(int i=0;i<n;i++)
for(int j=i+1;j<n+i+1;j++)
{
int num1 = Integer.parseInt(f.substring(0, i+1));
int num2 = Integer.parseInt(f.substring(i+1, j+1));
int num3 = Integer.parseInt(f.substring(j+1,f.length()));
int temp = check(num1,num2,num3);
if(temp == 0)
continue;
else
break;
}
System.out.println(count);
}
}