Գտեք տրված թվաքանակի ամենափոքր երկուական նիշը


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են Amazon Ֆուրկիտներ LinkedIn Microsoft Snapdeal
Լայնության առաջին որոնում Գծագիր

Խնդիրի հայտարարություն

«Գտիր տրված թվերի ամենափոքր երկուական թվանշանը» խնդիրը ասում է, որ քեզ տրվում է տասնորդական թիվ: Այսպիսով, գտիր N- ի ամենափոքր բազմապատիկը, որը պարունակում է միայն «0» և «1» երկուական թվանշաններ:

Օրինակ

37
111

Մանրամասն բացատրությունը կարելի է գտնել ներկառուցված նկարում ստորև:

Մոտեցում

Մոտեցումը կատարում է ա BFS անցում ՝ օգտագործելով «1» տողը ՝ որպես արմատային հանգույց: Մենք այս հանգույցին կցում ենք «0» և «1» և արդյունքում ստացված «10» և «11» տողերը մղում ենք դեպի հերթ, Ամեն անգամ հերթից մի տող դուրս գալուց հետո մենք «0» և «1» կցում ենք պոկված լարին և ստացված լարը հետ մղում հերթ: Անցնելու ընթացքում: Եթե ​​մենք գտնում ենք մի տող, որն ամբողջությամբ բաժանում է մուտքային համարը, մենք պարզապես վերադարձնում ենք այս տողը:

  1. Նվազեցնելով բարդությունը. Մենք նվազեցնում ենք մեր մոտեցման բարդությունը `կրճատելով դրանց թիվը տողերը մշակվում է BFS անցման ժամանակ: Յուրաքանչյուր մշակված տողի համար մենք ավելացնում ենք այն ՊՆ արժեքը (մնացորդը, երբ մշակված տողը բաժանվում է մուտքային համարով) a- ի հաշ հավաքածու, Եթե ​​որոշակի տողի համար, այս փոփոխության արժեքն արդեն առկա է հավաքածուի մեջ: Հետո, մենք տողը չենք ավելացնում BFS անցման հերթում:
  2. Պատճառը Բարդությունը նվազեցնելու համար մենք խուսափում ենք ավելացնել նույն տողերը ՊՆ արժեքը հերթում Դա այն դեպքում, եթե որոշակի փոփոխական արժեք ունեցող տողը արդեն առկա է հերթում կամ արդեն մշակված է: Հետո ցանկացած հաջորդ տող նույնով ՊՆ արժեքը չի ավելացվում հերթում: Սրա պատճառը. Ենթադրենք երկու տող X և Y նույն փոփոխական արժեքներով (մնացորդը, երբ մշակված տողը բաժանվում է մուտքային համարի վրա), X- ն արժեքով փոքր է Y- ից: Թող Z- ը լինի մեկ այլ լար, որը Y- ին կցվելիս մեզ տալիս է մի թիվ, որը բաժանվում է մուտքի համարի N.- ի, եթե այո, ապա մենք կարող ենք նաև այս տողը կցել X- ին, և այնուհանդերձ ստանալ թիվ մուտքային թիվով բաժանվող թիվ: Այսպիսով, մենք կարող ենք ապահով կերպով խուսափել B- ի հերթում Y ավելացնելուց:

Ալգորիթմ

  1. Ստեղծեք հերթ BFS անցում
  2. Ստեղծել հաշ հավաքածու ստուգելու համար, արդյոք առկա է որոշակի փոփոխական արժեք ունեցող տող, թե ոչ:
  3. Սկսեք BFS- ի անցումը `« 1 »աղբյուրի տողը հերթը մղելուց հետո:
  4. Դեպի անցման ժամանակ.
    1. Հերթից մի լար շեղեք:
    2. Ստուգեք դրա մոդուլային արժեքը
      1. եթե մոդուլային արժեքը 0 է, ապա այս տողը մերն է պահանջվող պատասխան.
      2. Այլապես, ստուգեք ՝ մոդուլային արժեքը հավաքածուում առկա է, թե ոչ:
  5. Եթե ​​այդ մոդուլային արժեքը առկա չէ հաշի հավաքածուում, ապա դուրս եկած տողին (տարբեր օրինակների) կցեք «0» և «1»:
  6. BFS- ի անցման հերթում ավելացրեք այս երկու տողերը, որոնք ձեռք են բերվել «0» և «1» հավելումներից հետո:
  7. կրկնել 4,5 և 6 քայլերը, մինչև գտնվի մուտքային տասնորդական թվաքանակի երկուական թիվ:

Ստորև նկարագրված է ալգորիթմը.

Գտեք տրված թվաքանակի ամենափոքր երկուական նիշը

Կոդ

C ++ ծածկագիր ՝ տրված համարի ամենափոքր երկուական նիշը բազմապատկելու համար

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

/* finds remainder when num is divided by N */
int mod(string num, int N)
{
    int value = 0;
    for(int i=0;i<num.length();i++)
    {
        value = 10*value + int(num[i] - '0');
        value %= N;
    }
    
    return value;
}

/* produces smallest binary digit multiple of given integer */
string smallestBinaryMultiple(int N)
{
    queue <string> q;
    unordered_set <int> us;
    
    string num = "1";
    q.push(num);
    
    /* BFS traversal */
    while(!q.empty())
    {
        string top = q.front(); q.pop();
        
        int modulus = mod(top,N);
        
        if(modulus == 0)
        return top;
        
        if(us.find(modulus) == us.end())
        {
            us.insert(modulus);
            q.push(top+"0");
            q.push(top+"1");
        }
    }
}

int main()
{
    int N = 37;
    cout<<smallestBinaryMultiple(N)<<endl;
    return 0;
}
111

Java կոդ ՝ տրված համարի ամենափոքր երկուական նիշը բազմապատիկը գտնելու համար

import java.util.*;
import java.io.*;

class TutorialCup 
{
    /* finds remainder when num is divided by N */
    static int mod(StringBuffer num, int N)
    {
        int value = 0;
        for(int i=0;i<num.length();i++)
        {
            value = 10*value + num.charAt(i) - '0';
            value %= N;
        }
        
        return value;
    }
    
    /* produces smallest binary digit multiple of given integer */
    static StringBuffer smallestBinaryMultiple(int N)
    {
        Queue <StringBuffer> q = new LinkedList<>();
        HashSet <Integer> us = new HashSet<Integer>();
        
        StringBuffer num = new StringBuffer("1");
        q.add(num);
        
        /* BFS traversal */
        while(!q.isEmpty())
        {
            StringBuffer top = q.poll();
            
            int modulus = mod(top,N);
            
            if(modulus == 0)
            return top;
            
            if(!us.contains(modulus))
            {
                us.add(modulus);
                
                StringBuffer appendZero = new StringBuffer(top);
                appendZero.append('0');
                
                StringBuffer appendOne = new StringBuffer(top);
                appendOne.append('1');
                
                q.add(appendZero);
                q.add(appendOne);
            }
        }
        
        return num;
    }

  public static void main (String[] args) 
  {
      int N = 37;
        System.out.println(smallestBinaryMultiple(N));
  }
}
111

Բարդության վերլուծություն

Timeամանակի բարդություն

T (n) = O (V + E), timeամանակի բարդությունը հավասար է այն տարրերի թվին, որոնց մենք հանդիպում ենք նախքան պահանջվող արդյունքին հասնելը:

Տիեզերական բարդություն

A (n) = O (V), Տիեզերական բարդությունը նույնպես կախված է նույն մետրից: Այն տարրերի քանակը, որոնց հանդիպում ենք նախքան պահանջվող արդյունքին հասնելը:

Այսպիսով, դժվար է պարզել, թե քանի հանգույց է ներկայանալու գծապատկերում, նախքան պահանջվող արդյունքին հասնելը:

V = հանգույցների քանակը

E = գրաֆիկի եզրեր