Pragalathan M
BAN USERThis can be solved in O(N), where N is the length of the word.
Lets assume,
 that the length of the word, N is given
 the machine returns 1 for each letter in test string matching the letter in dictionary word in the same index
private void findWord(int n) {
Character[] result = new Character[n];
char[] sample = new char[n];
int prevCount = 0;
for (int c = 'a'; c <= 'z'; c++) {
fillAll(sample, result, (char)c);
int count1 = checkWord(sample);
if (prevCount == count1) {
// the alphabet c never appeared in result; so skip and go to the next alphabet
continue;
}
c++; // go to next char
for (int i = 0; i < n; i++) {
char old = sample[i];
if (result[i] != null) {
// this index already has a valid char
continue;
} else {
sample[i] = (char) c;
}
int count2 = checkWord(sample);
if (count2 > count1) {
// c belongs to index i
count1++;
result[i] = (char)c;
} else if(count2<count1 ) {
// old char belongs to this index;
result[i] = old;
sample[i] = old;
}
}
prevCount = count1;
}
}
private void fillAll(char[] sample, Character[] result, char c) {
// file the index i of sample with char c where result[c] is null;
}
private int checkWord(char[] sample) {
// return the count of chars in sample, matching the corresponding index in the dictionary word
}
Here for each iteration of outer loop we complete two alphabets, hence it runs 13 time max.
The inner loop runs N times in worst case.
Hence the word can be guess in 13*N trials
There are two clues in the question.
1. its a 10 digit number
2. they are numbers
With these we can design a list of 10 bitsets where
 'i'th bit of 0th bitset will be 1 if the 'i'th row contains zero
 'i'th bit of 1st bitset will be 1 if the 'i'th row contains one
and so on.
when you get a number to search get the corresponding bitset for each digit and do an AND of collected sets. Now wherever you have one, that rows are the results.
Space: 10*n bits where n is the number of rows
Time for building: O(1) for finding the right bitset for each digit and O(1) for marking the row in the set. hence 10*n (~n)
Time for searching: O(1) for finding the right bitset for each digit and iterate over the bitset to find the final rows (i.e O(n))
A[i] newsets sets

1 {1} {1}
2 {2}, {1,2} {2}, {1,2}
3 {3}, {2,3}, {1,2,3} {3}, {2,3}, {1,2,3}
4 {4}, {3,4}, {2,3,4}, {1,2,3,4} {4}, {3,4}, {2,3,4}, {1,2,3,4}
5 {5}, {4,5}, {3,4,5}, {2,3,4,5}, {1,2,3,4,5} {5}, {4,5}, {3,4,5}, {2,3,4,5}, {1,2,3,4,5}

Pragalathan M
September 22, 2015 Time: O(n(n+1)/2)=n*n
Space: n(n+1)/2 // to store the limited number of subsets
n=length(A)
sets=[ ]
for (i=0 to n1)
newsets = [ ]
newsets.add( setof(A[i])
if(M == 1 && setof(A[i]) == SUM) print and break
foreach set in sets
s1 = sets[j].add(A[i])
if(s1.size == M && sum(s1)==SUM) print and break
newsets.add(s1); // we can also skip adding s1 if s1.size>M
sets.clear() // we dont need the old sets as we cant add next item to them
sets.addAll(newsets)
Lets say A= {1,2,3,4,5}
M=3
SUM=12
A[i] newsets sets

1 {1} {1}
2 {2}, {1,2} {2}, {1,2}
3 {3}, {2,3}, {1,2,3} {3}, {2,3}, {1,2,3}
4 {4}, {3,4}, {2,3,4}, {1,2,3,4} {4}, {3,4}, {2,3,4}, {1,2,3,4}
5 {5}, {4,5}, {3,4,5}, {2,3,4,5}, {1,2,3,4,5} {5}, {4,5}, {3,4,5}, {2,3,4,5}, {1,2,3,4,5}
in last iteration we have {3,4,5} whose sum is 12 and size is 3.
Now we went through A only once, but for each elements we iterated over sets which is i times hence n(n+1)/2.
In the last iteration we stored n(n+1)/2 items which is the max
<pre lang="" line="1" title="CodeMonkey97168" class="runthis">import java.util.ArrayList;
import java.util.List;
/**
*
* @author Pragalathan
*/
class CoinDenomination {
static class Coin {
int value;
int count;
public Coin(int value, int count) {
this.value = value;
this.count = count;
}
@Override
public String toString() {
return "(" + value + "x" + count + ")";
}
}
Coin[] coins;
public CoinDenomination(Coin[] coins) {
this.coins = coins;
}
List<Coin> getChange(int amount) {
List<Coin> change = new ArrayList<Coin>();
getChange(amount, 0, change);
return change;
}
private boolean getChange(int balance, int coinIndex, List<Coin> change) {
if (coinIndex >= coins.length) {
return false;
}
Coin coin = coins[coinIndex];
int count = Math.min(coin.count, balance / coin.value);
for (int i = count; i >= 0; i) {
int newBalance = balance  i * coin.value;
if (newBalance == 0) {
change.add(new Coin(coin.value, i));
return true;
}
if (getChange(newBalance, coinIndex + 1, change)) {
if (i > 0) {
change.add(new Coin(coin.value, i));
}
return true;
}
}
return false;
}
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
int[] values = {1, 5, 10, 25, 50, 100};
int[] counts = {3, 4, 2, 4, 1, 2};
Coin[] coins = new Coin[values.length];
for (int i = 0; i < values.length; i++) {
coins[i] = new Coin(values[i], counts[i]);
}
CoinDenomination cd = new CoinDenomination(coins);
int amount = 33;
System.out.println(amount + ": " + cd.getChange(amount));
values = new int[]{1, 10, 25, 50, 100};
counts = new int[]{3, 3, 4, 1, 2};
coins = new Coin[values.length];
for (int i = 0; i < values.length; i++) {
coins[i] = new Coin(values[i], counts[i]);
}
cd = new CoinDenomination(coins);
amount = 205;
System.out.println(amount + ": " + cd.getChange(amount));
}
}
</pre><pre title="CodeMonkey97168" input="yes">
</pre>
Repannadwilliams31, Applications Developer at National Instruments
I am Anthony, Human Resources specialist with a decade of successful experience in hiring and employee management.I am a ...
Repdavisjerryh, Backend Developer at Abs india pvt. ltd.
For the last two years, I am Effectively managing the teamâ€™s performance, conducting regular performance reviews and appraisals, and ...
Open Chat in New Window
create an int array A, of size 26 and initialize to 0
 Pragalathan M September 24, 2015for each letter S[i], in given string, if it is alphabet, then A[lower(S[i])'a']++
iterate over A and return false if you find any A[i] equal to 0