CODEWITHSUNDEEP
algorithmsearchlanguage-agnosticlogiccombinations
stak
stak

Reputation: 149

How to find a number from its 3 digit combinations?

If there is a 8 digit number 65478209 (the digits in the number can repeat) and given the combinations are always in the order of the number, then if all combinations 8c3 = 56 combinations are given then what will be the shortest solution to find out the number(s) ?

An example scenario could be a bank login where user need to enter 3 random digits of their code like 3rd, 5th and 6th, where this is one of the 8c3 combination. So if all 8c3 combinations are given then what will be the solution/logic to find the number? (or first number if there are more numbers as a solution)

For problem solving in programming language, the input will an array of 56 3 digit combinations, and we have to find the code which is "65478209" or whatever.

Upvotes: 1

Views: 372

Answers (2)

Hexoul
Hexoul

Reputation: 161

How about using permutation? I write the simple code in c++ style. Check it.

int k = 3;
string digit = "65478209";
int digitLen = digit.length();

int* indexArr = new int[digitLen];
for(int i=0; i < digitLen; i++) indexArr[i] = i;

do
{
    bool isInOrder=true;
    string ret = "";
    for(int i=1; i < k; i++) if(indexArr[i] < indexArr[i-1])
    {
        isInOrder = false;
        break;
    }
    if(!(isInOrder)) continue;

    for(int i=0; i < k; i++) ret += digit[indexArr[i]];
} while(next_permutation(indexArr, indexArr+digitLen));

delete indexArr;

Edit

here is my solution.

vector<string> combinations;
set<int> includedDigit;
vector<int> referCnt;

// Get reference count from all precedences
for(int i=0; i < combinations.size(); i++)
{
    string e = combinations[i];
    for(int j=0; j < k-1; j++)
    {
        includedDigit.insert(e.at(j) - '0');
        for(int l=j+1; l < k; l++)
        {
            int curDigit = e.at(l) - '0';
            referCnt.push_back(curDigit);
        }
    }
}

// Sorting reference counts with digit
vector<pair<int,int>> ret;
for(int i=0; i < 10; i++)
{
    int digitCnt = count(referCnt.begin(), referCnt.end(), i);
    if(digitCnt == 0 && includedDigit.find(i) != includedDigit.end()) ret.push_back(make_pair(1, i));
    else if(digitCnt != 0) ret.push_back(make_pair(digitCnt, i));
}
sort(ret.begin(), ret.end());

// Print the result
for(auto it=ret.begin(); it != ret.end(); it++)
{
    pair<int,int> val = *it;
    cout << val.second;
}

It works although I think it can be shorten. In addition, if original digit is not kind of permutation, it should be more complex.

Upvotes: 2

FallAndLearn
FallAndLearn

Reputation: 4135

k = 3

The following recursive algorithm picks all of the k-element combinations from an ordered set:

  1. Choose i as first element.
  2. Combine i with each of the combinations of k-1 elements chosen recursively from the set of elements larger than i.
  3. Iterate the above for each i in the set.

Upvotes: 0

Related Questions