CODEWITHSUNDEEP
algorithmnumberspuzzle
CodeQuestor
CodeQuestor

Reputation: 911

Any algorithm to find the double trouble number?

I was trying to code the double trouble number problem, but before that not able to finalize the algorithm. Anybody has any idea?

Problem Statement -

The numbers has the following property -

Whenever you would right-rotate the number (that is, take away the last digit and put it in front of the number), you would end up with double the original number. Numbers possessing this property were called double-trouble numbers. For example, X = 421052631578947368 is a double-trouble number, since 2X = 842105263157894736 which is a right rotation of X.

The number X is a double-trouble number in the number system with base 10. Any number system with base p >= 2 , however, has many such double-trouble numbers. In the binary number system (base p = 2), for example, we have the double-trouble numbers 01 and 0101. Notice that the leading zeros are necessary here in order to obtain the proper number after right rotation.

In the binary number system the smallest double-trouble number is 01. In > the decimal (p = 10) number system, the smallest double-trouble number is 052631578947368421. I need to write a program that computes for a given base p of a number system the smallest double-trouble number in that system.

Upvotes: 2

Views: 419

Answers (1)

Louis Ricci
Louis Ricci

Reputation: 21106

Here's the brute force solution in JavaScript. It starts with a digit, then prepends the double of the previous digit (plus carry). After each iteraion it tests if the digits are a double trouble number (it also tries the prepend by "0" corner/ambiguous case)

This implementation is only for base 10; you'll have to understand the algorithm and modify the code to create an arbitrary base abstraction.

Double Trouble Solver for base 10

// (digits * 2) == digits[n]:digits[1..n-1]
function isDT(digits) {
    var times2 = "";
    var carry = false;
    for(var i = digits.length-1; i >= 0; i--) {
        var d = parseInt(digits.charAt(i));
        var d2 = "" + (d * 2 + (carry ? 1 : 0));
        carry = d2.length > 1;
        times2 = d2.charAt(d2.length > 1 ? 1 : 0) + times2;
    }
    if(carry) { times2 = "1" + times2; }
    return times2 == (digits.charAt(digits.length -1) + digits.substring(0, digits.length -1));
}
// generate a doule trouble number from a starting digit
function makeDT(digits, carry) {
    var carry = carry || false;
    var digits = "" + digits;
    if(carry && isDT("1" + digits)) {
        return "1" + digits;
    } else if(isDT(digits)) {
        return digits;
    } else if(isDT("0" + digits)) {
        return "0" + digits;
    }
    var d = digits.charAt(0);
    var d2 = "" + (d * 2 + (carry ? 1 : 0));
    carry = d2.length > 1;
    digits = d2.charAt(d2.length > 1 ? 1 : 0) + digits;
    return makeDT(digits, carry);
}
//
alert(makeDT("9"));
alert(makeDT("8"));
alert(makeDT("7"));
alert(makeDT("6"));
alert(makeDT("5"));
alert(makeDT("4"));
alert(makeDT("3"));
alert(makeDT("2"));
alert(makeDT("1"));

EDIT Here's the jsfiddle http://jsfiddle.net/avbfae0w/

Upvotes: 2

Related Questions