Jump to content
Raul

[Easy] Algo challenge #2

Recommended Posts

De data aceasta, propun un challenge care nu necesita prea multe cunostinte in structuri de date, ci o logica buna.

 

O definitie necesara: In matematica, un numar Kaprekar, pentru o baza data, este un numar intreg si pozitiv, al carui valoare ridicata la patrat, in aceeasi baza, poate fi impartita in doua bucati, iar suma numerelor din aceste doua bucati rezulta efectiv in numarul original. Numarul se imparte in doua parti egale (sau +1 la una dintre parti, atunci cand este un numar impar de cifre), nu se fac "variante". Exemplu: 45 este un numar care respecta regula (numar Kaprekar), deoarece 45² = 2025 si 20+25 = 45.

Alte exemple: 9 respecta regula, deoarece 9² = 81 si 8+1 = 9; 297 respecta regula, deoarece 297² = 88209 si 88 + 209 = 297.

ATENTIE: Aceasta nu reprezinta definitia oficiala in totalitate, este o variatie, problema trebuie rezolvata pe baza la ce se spune aici.

 

A se observa ca in ultimul exemplu, numarul ridicat la patrat se imparte intr-o bucata de lungime doi si celalalta de lungime trei, deoarece are un numar impar de cifre, fata de cazurile in care ar fi un numar par de cifre. De asemenea, trebuie avut grija, daca una dintre cele doua bucati incepe cu un 0.

 

Se dau doua numere intregi, p si q, si se cere sa se afiseze toate numerele Kaprekar din respectivul interval (inclusiv p si q); 0 < p < q < 100000

Exemplu: p = 1, q = 100; se va afisa "1 9 45 55 99", acestea fiind numerele care respecta regula.

 

Limbajul care va fi folosit este la alegere libera. Solutiile cu complexitate timp mai mare decat O(N) sunt respinse. O solutie personala va fi pusa ulterior.

Spor!

Edited by Raul
  • Like 1
  • Upvote 1
Link to comment
Share on other sites

public class MuieGO {

	public static void main(String[] args) {
		
		int p=1;
		int q=10000000;
		long startTime = System.currentTimeMillis();
		for (int i = p; i <= q; i++) {
			if(check(i))System.out.print(i+"  ");
		}
		System.out.println();
		System.out.println(System.currentTimeMillis()-startTime + " milliseconds");
	}

	static boolean check(long nr) {
		long numar = nr * nr;
		int lungime = String.valueOf(numar).length();
		long jum1 = 0, jum2 = 0;
		if (lungime % 2 == 0) {
			jum1 = (long) (numar / Math.pow(10, (lungime / 2)));
			jum2 = (long) (numar % Math.pow(10, (lungime / 2)));
		} else {
			jum1 = (long) (numar / Math.pow(10, (lungime / 2) + 1));
			jum2 = (long) (numar % Math.pow(10, (lungime / 2) + 1));
		}

		return (jum1 + jum2 == nr);
	}
}

1  9  45  55  99  297  703  999  2223  2728  4950  5050  7272  7777  9999  17344  22222  77778  82656  95121  99999  142857  148149  181819  187110  208495  318682  329967  351352  356643  390313  461539  466830  499500  500500  533170  538461  609687  643357  648648  670033  681318  791505  812890  818181  851851  857143  961038  994708  999999  4444444  4927941  5072059  5555556  9372385  9999999  
2319 milliseconds
 

Edited by theandruala
  • Like 1
Link to comment
Share on other sites

39 minutes ago, theandruala said:

public class MuieGO {

	public static void main(String[] args) {
		
		int p=1;
		int q=10000000;
		long startTime = System.currentTimeMillis();
		for (int i = p; i <= q; i++) {
			if(check(i))System.out.print(i+"  ");
		}
		System.out.println();
		System.out.println(System.currentTimeMillis()-startTime + " milliseconds");
	}

	static boolean check(long nr) {
		long numar = nr * nr;
		int lungime = String.valueOf(numar).length();
		long jum1 = 0, jum2 = 0;
		if (lungime % 2 == 0) {
			jum1 = (long) (numar / Math.pow(10, (lungime / 2)));
			jum2 = (long) (numar % Math.pow(10, (lungime / 2)));
		} else {
			jum1 = (long) (numar / Math.pow(10, (lungime / 2) + 1));
			jum2 = (long) (numar % Math.pow(10, (lungime / 2) + 1));
		}

		return (jum1 + jum2 == nr);
	}
}

1  9  45  55  99  297  703  999  2223  2728  4950  5050  7272  7777  9999  17344  22222  77778  82656  95121  99999  142857  148149  181819  187110  208495  318682  329967  351352  356643  390313  461539  466830  499500  500500  533170  538461  609687  643357  648648  670033  681318  791505  812890  818181  851851  857143  961038  994708  999999  4444444  4927941  5072059  5555556  9372385  9999999  
2319 milliseconds
 

Am testat, solutia este valida, kudos! :)

Sunt binevenite si alte propuneri, in continuare.

Edited by Raul
Link to comment
Share on other sites

Salut,  mi se pare mie sau algoritmul prezentat de theandruala nu merge chiar asa bine ?

Mai sunt numere care sunt Kaprekar, dar nu sunt afisate: de exemplu 4879

 

#include <iostream>

using namespace std;

bool isKaprekar(uint64_t k)
{
    uint64_t q, r, n = 10, kp = k*k;

    if(k == 1) return true;

    while(kp > n)
    {
        q = kp/n;
        r = kp%n;
        if(q + r == k && q > 0 && r > 0) return true;
        n *= 10;
    }
    return false;
}

int main()
{
    uint64_t p, q, i;
    cin>>p>>q;

    for(i=p; i<=q; i++)
        if(isKaprekar(i)) cout<<i<<" ";

    return 0;
}
Link to comment
Share on other sites

1 hour ago, TheOne01 said:

Salut,  mi se pare mie sau algoritmul prezentat de theandruala nu merge chiar asa bine ?

Mai sunt numere care sunt Kaprekar, dar nu sunt afisate: de exemplu 4879

 


#include <iostream>

using namespace std;

bool isKaprekar(uint64_t k)
{
    uint64_t q, r, n = 10, kp = k*k;

    if(k == 1) return true;

    while(kp > n)
    {
        q = kp/n;
        r = kp%n;
        if(q + r == k && q > 0 && r > 0) return true;
        n *= 10;
    }
    return false;
}

int main()
{
    uint64_t p, q, i;
    cin>>p>>q;

    for(i=p; i<=q; i++)
        if(isKaprekar(i)) cout<<i<<" ";

    return 0;
}

 

4879 ^ = 23804641

2380 + 4641 NU DA 4879

Link to comment
Share on other sites

18 hours ago, TheOne01 said:

Salut,  mi se pare mie sau algoritmul prezentat de theandruala nu merge chiar asa bine ?

Mai sunt numere care sunt Kaprekar, dar nu sunt afisate: de exemplu 4879

 


#include <iostream>

using namespace std;

bool isKaprekar(uint64_t k)
{
    uint64_t q, r, n = 10, kp = k*k;

    if(k == 1) return true;

    while(kp > n)
    {
        q = kp/n;
        r = kp%n;
        if(q + r == k && q > 0 && r > 0) return true;
        n *= 10;
    }
    return false;
}

int main()
{
    uint64_t p, q, i;
    cin>>p>>q;

    for(i=p; i<=q; i++)
        if(isKaprekar(i)) cout<<i<<" ";

    return 0;
}

Exemplul dat cu 4879 este gresit, nefiind un numar Kaprekar (pe baza definitiei din textul problemei), dupa cum a demonstrat si Andruk. Bazeaza-te pe definita data in textul problemei, nu pe altceva. Am modificat acum ca sa fie mai clar, acum sigur nu mai sunt dileme. Imi pare rau pentru confuzia creata!

 

Rezolvarea ta nu este corecta, ai 3/7 testcase-uri care pica. In principal, problema e ca nu validezi corect si apar numere care nu sunt Kaprekar (evident, pe baza definitiei din textul problemei). Exemplu:

Input: p = 1000, q = 10000
Output asteptat: 2223 2728 4950 5050 7272 7777 9999
Output-ul tau: 2223 2728 4879 4950 5050 5292 7272 7777 9999 

 

 

LE: Solutia mea (Golang) este urmatoarea:

func kaprekar(p, q int64) {
    for i := p; i <= q; i++ {
        x := i * i
        xS := len(fmt.Sprintf("%d", x))
        if xS % 2 == 1 {
            xS++
        }
        d := int64(math.Pow(10, float64(xS/2)))
        l, r := x / d, x % d
        if i == l + r {
            fmt.Printf("%d ", i)
        }
    }
}

* Problema este adaptata de la ceva asemanator gasit pe HackerRank

Edited by Raul
Link to comment
Share on other sites

3 hours ago, TheOne01 said:

Nu cred ca la inceput era specificat ca cele doua jumatati sa fie egale. Oricum am inteles :D Multumesc !

Mi-am dat seama ca nu se intelegea foarte clar treaba asta, de aceea am si modificat, acum sigur nu mai sunt dileme.

Link to comment
Share on other sites

import math

def isKaprekar(a):
    n = (int)(math.pow(a, 2))
    n_arr = [int(i) for i in str(n)]
    midd = 0

    # take care of the numbers lt 10:
    if a == 1:
        return True
    if n < 10:
        return False

    if n % 2 == 0:
        midd = (int)(len(n_arr) / 2)
    else:
        midd = (int)(len(n_arr) / 2)

    if( (int)(''.join(str(x) for x in n_arr[0:midd])) +
        (int)(''.join(str(x) for x in n_arr[midd :])) == a):
        return True
    else:
        return False

for i in range(0, 10001):
    # print(i)
    if isKaprekar(i):
        print(i)

PiTong

Link to comment
Share on other sites

Just now, urs said:

import math

def isKaprekar(a):
    n = (int)(math.pow(a, 2))
    n_arr = [int(i) for i in str(n)]
    midd = 0

    # take care of the numbers lt 10:
    if a == 1:
        return True
    if n < 10:
        return False

    if n % 2 == 0:
        midd = (int)(len(n_arr) / 2)
    else:
        midd = (int)(len(n_arr) / 2)

    if( (int)(''.join(str(x) for x in n_arr[0:midd])) +
        (int)(''.join(str(x) for x in n_arr[midd :])) == a):
        return True
    else:
        return False

for i in range(0, 10001):
    # print(i)
    if isKaprekar(i):
        print(i)

PiTong

da, stiu ca se putea mai dragut cu impartit/modulus cu puteri ale lui 10, da' astia suntem, cu astia defilam.

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.



×
×
  • Create New...