Page 2 of 2 FirstFirst 12
Results 21 to 28 of 28
  1. #21
    gusgol is offline Member
    Join Date
    Apr 2009
    Posts
    3
    Rep Power
    0

    Default Entire problem

    Hello..

    Yes, this thread is only part of the problem.

    The entire problem is:

    We must find the 12nd number that

    original number *8/3 = number modified(1234 -->4123);


    INCORRECT EXAMPLE : 1234 * 8 /3 = 4123 --> 1234*8/3 != 4123
    CORRECT EXAMPLE: : 27 * 8 / 3 = 72



    See the entire search for the 12nd number:
    1. Original number: 27 - Modified number: 72
    2. Original number: 2727 - Modified number: 72
    3. Original number: 116883 - Modified number: 311688
    4. Original number: 155844 - Modified number: 415584
    5. Original number: 194805 - Modified number: 519480
    6. Original number: 233766 - Modified number: 623376
    7. Original number: 272727 - Modified number: 727272
    8. Original number: 311688 - Modified number: 831168
    9. Original number: 350649 - Modified number: 935064
    10. Original number: 27272727 - Modified number: 72727272
    11. Original number: 2727272727 - Modified number: 7272727272
    12. Original number: 116883116883 - Modified number: 311688311688


    We need to create a efficient algorithm, althoug the problem will spend hours to find the 12nd number. And, thats why using only integers besides using String.

    Does anyone knows an efficient way to do this search? Thx everybody for ur participation!!!

  2. #22
    gusgol is offline Member
    Join Date
    Apr 2009
    Posts
    3
    Rep Power
    0

    Default

    Hello..

    Yes, this thread is only part of the problem.

    The entire problem is:

    We must find the 12nd number that

    original number *8/3 = number modified(1234 -->4123);


    INCORRECT EXAMPLE : 1234 * 8 /3 = 4123 --> 1234*8/3 != 4123
    CORRECT EXAMPLE: : 27 * 8 / 3 = 72



    See the entire search for the 12nd number:
    1. Original number: 27 - Modified number: 72
    2. Original number: 2727 - Modified number: 72
    3. Original number: 116883 - Modified number: 311688
    4. Original number: 155844 - Modified number: 415584
    5. Original number: 194805 - Modified number: 519480
    6. Original number: 233766 - Modified number: 623376
    7. Original number: 272727 - Modified number: 727272
    8. Original number: 311688 - Modified number: 831168
    9. Original number: 350649 - Modified number: 935064
    10. Original number: 27272727 - Modified number: 72727272
    11. Original number: 2727272727 - Modified number: 7272727272
    12. Original number: 116883116883 - Modified number: 311688311688


    We need to create a efficient algorithm, althoug the problem will spend hours to find the 12nd number. And, thats why using only integers besides using String.

    Does anyone knows an efficient way to do this search? Thx everybody for ur participation!!!

  3. #23
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,565
    Rep Power
    12

    Default

    Just a small point: 116883116883 is somewhat large to be dealt with using int variables. If you are allowed to use them, use long. (Of course, some might regard it as an "intellectual question" how to use int...)

    Personally, I'd wonder if a little number theory might arrive at a solution faster than computation. Or at any rate suggest speedups. But I won't wonder that in any detail for fear of offending against OrangeDog's injunction not to criticise. So, go at it with brute force and grim determination: and call that an "interesting intellectual question".

  4. #24
    OrangeDog's Avatar
    OrangeDog is offline Senior Member
    Join Date
    Jan 2009
    Location
    Cambridge, UK
    Posts
    838
    Rep Power
    6

    Default

    The question doesn't say you have to use brute force and grim determination. Finding a better way to do it is indeed an "interesting intellectual question". I have other things to be getting on with myself or I would do the whole thing for funsies.

    Hint: there's a clear pattern involving the combinations 27 and 116(883). Does 155844155844 satisfy the condition?
    Last edited by OrangeDog; 04-20-2009 at 03:39 AM.
    Don't forget to mark threads as [SOLVED] and give reps to helpful posts.
    How To Ask Questions The Smart Way

  5. #25
    DavidG24 is offline Member
    Join Date
    Apr 2009
    Posts
    49
    Rep Power
    0

    Default Re Invert Integer

    hey mate,

    well this is much more difficult than the original problem posted.

    Just before I begin the mathematics, I want to be 100% clear that you seek to find a integer n such that

    n x ( 8 / 3) = reversed(n)

    if n does not have to be an integer, the simple solution is

    n = (3 / 8) * reversed(n)

    although I doubt it would be that simple.


    Okay, first off let m = reversed(n) --> n = reversed(m) (or lets impose)

    then our expression becomes,

    reversed(m) = m x ( 8 / 3)

    given m is an integer, then we know 8*m is an integer, however to ensure (8 *m) / 3 is definately an integer we must ensure that
    8*m = 8*(3k) ; k being any integer ( i.e. it is divisible by 3 )
    There are many forms in which we may put 8*m to ensure its divisible by 3, however one of the simplest forms would be
    8 *m = 8 * k * (k + 1) * (k + 2) for all integers k.
    and mainly
    m = k^3 + 3*k^2 + 2*k

    This unfortunately is only 1/100 th of the problem,

    given m would yield a number of the form (impose order p)

    m = k^3 + 2*k^2 + 2*k = sum ( a(i) * 10^(i) , i = 0 to p)
    whereby a(i) are O(1) integers (i.e. single digits)
    then we need to solve k, such that
    8 * ( k^3 + 2*k^2 + 2*k) = reversed(m)
    As reversed(m) has the same order we arrive at
    8 * (k^3 + 2*k^2 + 2*k) = sum( a(p - i) * 10^(i) )

    hmmmm, I can't say I would know a definative way of attacking this head on however, if you where to impose a brute force technique, the following may work,


    private static int find_reverse_int(){
    int k = 1; // k = 0 holds
    int temp;
    count = 1;
    while (count <= 12){

    temp = 8 * (k^3 + 2*k^2 + 2*k) //evaluate the powers using the Math.pow method - however make sure to cast back to an int

    if(temp/3 == reversed(temp)){
    count++
    }

    k++;

    }
    return temp;
    }

    whereby reversed(temp) can be achieved using the techniques provided already. The only hesitation I would have with this is the infinate loop this may create, however you have shown certain values that do work.

    Hope this helps,

    David

    ps - I will have a look at this in more detail tonight and hopefully will be able to provide a more substantial algorithm ( I know what I've provided is weak at best!)
    Last edited by DavidG24; 04-21-2009 at 10:49 AM.

  6. #26
    angryboy's Avatar
    angryboy is offline Senior Member
    Join Date
    Jan 2009
    Posts
    742
    Rep Power
    6

    Default

    Interesting indeed... I've done some digging on google and came across this page: Nabble - java.net - soujava java-list - [Desavio] Algoritimo pouco eficiente.
    Its in Portuguese and here's the OP by using google trans:
    Oops,
    I'm doing the chair Complexity of Algorithm, and I'm breaking my head to solve a challenge of the teacher quickly.
    The algorithm must find the twelfth number that the connection algorithm described below:
    The algorithm can have only integer variables (int, long ...)
    Take the last digit of the number and goes to front, example 12345 becomes 51,234
    is multiplied by 8 / 3 and this number must be the same as the number of entry, example 51,234 multiplied by the 8 / 3 to be considered by the algorithm should result 12345.

    What I already checked.
    * The MMC of 8 / 3 is 24, so the meter can be done in 24 in 24.

    Problem:
    * The program is taking over an hour to find the seventh number.

    My code then attached: TestIntPalindromo.java

    Who has some idea of how to improve means this algorithm.

    Thanks already gurizada.
    There's a solution posted similar to David's above, but the concluding posts towards the end seems to mark this problem as NP-Complete.

    Here's the link given:
    Linear programming - Wikipedia, the free encyclopedia
    P = NP problem - Wikipedia, the free encyclopedia
    USE CODE TAGS--> [CODE]...[/CODE]
    Get NotePad++ (free)

  7. #27
    corlettk is offline Member
    Join Date
    Apr 2009
    Location
    Brisbane
    Posts
    86
    Rep Power
    0

    Default

    Quote Originally Posted by OrangeDog View Post
    You can do it in place using either a single temp char variable or using XORs to swap the values.
    Huh XOR? Let's see... 'A'==41 XOR 'B'==42
    Java Code:
        101001
    XOR 101010
    =   000011 = 3
    Nope I'm definately missing something. Care to clue me in? Please?

  8. #28
    OrangeDog's Avatar
    OrangeDog is offline Senior Member
    Join Date
    Jan 2009
    Location
    Cambridge, UK
    Posts
    838
    Rep Power
    6

    Default

    to swap x and y:
    Java Code:
    y = x ^ y;
    x = x ^ y;
    y = x ^ y;
    Though it's much easier to see what you're doing if you use a temporary variable. You'd mostly use this when programming in assembler with limited number of registers.

    This works because XOR is a self-inverting operation. For any x, x^x = 0 and x^0 = x. Therefore x^y^x = y.
    Last edited by OrangeDog; 04-20-2009 at 04:11 PM.
    Don't forget to mark threads as [SOLVED] and give reps to helpful posts.
    How To Ask Questions The Smart Way

Page 2 of 2 FirstFirst 12

Similar Threads

  1. How to convert Integer[] to int[]
    By Nithya in forum New To Java
    Replies: 26
    Last Post: 02-11-2010, 05:41 PM
  2. Integer to String
    By zervine in forum Forum Lobby
    Replies: 3
    Last Post: 09-12-2008, 12:07 PM
  3. Integer length
    By jithan in forum New To Java
    Replies: 1
    Last Post: 06-12-2008, 03:35 PM
  4. How to get Integer from table
    By adeeb in forum AWT / Swing
    Replies: 1
    Last Post: 06-10-2008, 11:56 AM
  5. Integer vs int
    By bugger in forum New To Java
    Replies: 1
    Last Post: 11-14-2007, 09:13 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •