ദീർഘചതുരം ലീറ്റ്കോഡ് പരിഹാരം നിർമ്മിക്കുക


വൈഷമ്യ നില എളുപ്പമായ
മഠം

നിങ്ങൾ ഒരു വെബ് ഡിസൈനറാണെന്ന് ദീർഘചതുരം ലീറ്റ്കോഡ് പരിഹാരം നിർമ്മിക്കുന്ന പ്രശ്നം പറയുന്നു. മുൻകൂട്ടി നിർവചിച്ച ഏരിയ ഉപയോഗിച്ച് ഒരു വെബ് പേജ് രൂപകൽപ്പന ചെയ്യുന്നതിന് നിങ്ങൾക്ക് ഒരു ചുമതല നൽകിയിട്ടുണ്ട്. രൂപകൽപ്പനയിൽ ചില നിയന്ത്രണങ്ങൾ ഏർപ്പെടുത്തിയിട്ടുണ്ട്. വെബ് പേജിന്റെ ദൈർഘ്യം വെബ് പേജിന്റെ വീതിക്ക് വലുതോ തുല്യമോ ആയിരിക്കണം, രൂപകൽപ്പന ചെയ്ത വെബ് പേജിന്റെ വിസ്തീർണ്ണം നൽകിയ ഏരിയയ്ക്ക് തുല്യമായിരിക്കണം. അവസാനത്തേത് എന്നാൽ ഏറ്റവും കുറഞ്ഞത്, നീളവും വീതിയും തമ്മിലുള്ള വ്യത്യാസം കഴിയുന്നത്ര ചെറുതായിരിക്കണം. അതിനാൽ, പ്രശ്നം പരിഹരിക്കുന്നതിന് ആഴത്തിൽ മുങ്ങുന്നതിന് മുമ്പ് കുറച്ച് ഉദാഹരണങ്ങൾ നോക്കാം.

ദീർഘചതുരം ലീറ്റ്കോഡ് പരിഹാരം നിർമ്മിക്കുക

area = 4
[2,2]

വിശദീകരണം: 4 ന് തുല്യമായ ഏരിയയുള്ള വെബ് പേജിന്റെ നീളവും വീതിയും 1 × 4 അല്ലെങ്കിൽ 2 × 2 ആകാം. എന്നാൽ നീളവും വീതിയും തമ്മിൽ അവ തമ്മിൽ കുറഞ്ഞ വ്യത്യാസമുള്ളതായി ഞങ്ങൾ കണ്ടെത്തേണ്ടതുണ്ട്. 2 × 2 അളവുകൾ തിരഞ്ഞെടുക്കുന്നതാണ് നല്ലത്. നീളം പേജിന്റെ വീതിക്ക് വലുതോ തുല്യമോ ആണെന്നും 2 × 2 അളവ് പിന്തുടരുന്നു.

area = 23
[23, 1]

വിശദീകരണം: നിങ്ങൾക്ക് ഏരിയ = 23 ഉള്ള രണ്ട് വെബ് പേജുകൾ മാത്രമേ ഉണ്ടാകൂ. നിങ്ങൾക്ക് ഒന്നുകിൽ 23 × 1 അല്ലെങ്കിൽ 1 × 23 അളവുകൾ ഉണ്ടായിരിക്കാം. 1 × 23 അളവുകളുള്ള വെബ് പേജ് ഞങ്ങളുടെ ആദ്യ വ്യവസ്ഥയെ ലംഘിക്കുന്നതിനാൽ. ഞങ്ങൾക്ക് 23 × 1 വലുപ്പമുള്ള വെബ് പേജ് മാത്രമേ ഉണ്ടാകൂ.

ദീർഘചതുരം ലീറ്റ്കോഡ് പരിഹാരം നിർമ്മിക്കുന്നതിനുള്ള സമീപനം

മുൻ‌കൂട്ടി നിർ‌വ്വചിച്ച ഏരിയ ഉപയോഗിച്ച് വെബ് പേജിന്റെ അനുയോജ്യമായ വലുപ്പം കണ്ടെത്താൻ ദീർഘചതുരം ലീറ്റ്കോഡ് പരിഹാരം നിർമ്മിക്കുന്ന പ്രശ്നം ഞങ്ങളോട് ആവശ്യപ്പെടുന്നു. വെബ്‌പേജ് അളവുകൾ‌ അടിച്ചേൽപ്പിച്ച നിയന്ത്രണങ്ങൾ‌ നിറവേറ്റണം. മൂന്ന് പരിമിതികൾ ഇവയാണ്: നീളം വെബ് പേജിന്റെ വീതിക്ക് വലുതോ തുല്യമോ ആയിരിക്കണം, രൂപകൽപ്പന ചെയ്ത വെബ് പേജിന്റെ വിസ്തീർണ്ണം നൽകിയ ഏരിയയ്ക്ക് തുല്യമായിരിക്കണം, നീളവും വീതിയും തമ്മിലുള്ള വ്യത്യാസം കുറഞ്ഞത് ആയിരിക്കണം. തന്നിരിക്കുന്ന സ്ഥലത്തിന്റെ 1 മുതൽ സ്‌ക്വയർ റൂട്ട് വരെ പൂർണ്ണസംഖ്യകളിലൂടെ ലൂപ്പുചെയ്യുന്നതിലൂടെ നൽകിയ പരിമിതികളെ തൃപ്തിപ്പെടുത്തുന്ന ഒരു കൂട്ടം അളവുകൾ നമുക്ക് എളുപ്പത്തിൽ കണ്ടെത്താൻ കഴിയും. നിലവിലെ സംഖ്യ പ്രദേശത്തെ വിഭജിക്കുന്നുണ്ടോയെന്ന് ഞങ്ങൾ പരിശോധിച്ചുകൊണ്ടിരിക്കുന്നു. അങ്ങനെയാണെങ്കിൽ‌, അതിന്റെ ക p ണ്ടർ‌പാർ‌ട്ട് തമ്മിലുള്ള വ്യത്യാസം (തന്നിരിക്കുന്ന ഏരിയയെ നിലവിലെ സംഖ്യയാൽ വിഭജിച്ച് ലഭിച്ച ഘടകത്തിന്) നിലവിലെ സെറ്റിനേക്കാൾ കുറഞ്ഞ വ്യത്യാസമുണ്ടോ എന്ന് ഞങ്ങൾ പരിശോധിക്കുന്നു. എല്ലാ നിബന്ധനകളും പാലിക്കുകയാണെങ്കിൽ, ഞങ്ങൾ ഉത്തരം അപ്‌ഡേറ്റുചെയ്യുന്നു.

തുടക്കത്തിൽ, ഞങ്ങൾ ഉത്തരം ഏരിയാ 1 ആയി സജ്ജമാക്കി, കാരണം ഇത് എല്ലായ്പ്പോഴും നൽകിയിരിക്കുന്ന പരിമിതികളെ തൃപ്തിപ്പെടുത്തുന്നു. പരിഹാരത്തിൽ, അവയ്ക്കിടയിൽ കുറഞ്ഞ വ്യത്യാസമുള്ള ഒരു മികച്ച സെറ്റ് കണ്ടെത്താൻ ഞങ്ങൾ ശ്രമിക്കുന്നു. അവസാനം, ഞങ്ങൾ അളവുകൾ ഒരു ആയി നൽകുന്നു ശ്രേണി.

ദീർഘചതുരം ലീറ്റ്കോഡ് പരിഹാരം നിർമ്മിക്കുന്നതിനുള്ള കോഡ്

സി ++ കോഡ്

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

vector<int> constructRectangle(int area) {
    vector<int> ans({area, 1});
    for(int i=1;i*i<=area;i++){
        if(area%i == 0 && (area/i - i)<(ans[0] - ans[1]))
            ans[0] = area/i, ans[1] = i;
    }
    return ans;
}

int main(){
    vector<int> ans = constructRectangle(4);
    cout<<ans[0]<<", "<<ans[1];
}
2, 2

ജാവ കോഡ്

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

class Main
{
    public static int[] constructRectangle(int area) {
        int[] ans = {area, 1};
        for(int i=1;i*i<=area;i++){
            if(area%i == 0 && (area/i - i)<(ans[0] - ans[1])){
                ans[0] = area/i;
                ans[1] = i;
            }
        }
        return ans;
    }
    
  public static void main (String[] args) throws java.lang.Exception{
    int[] ans = constructRectangle(4);
    
    System.out.println(ans[0] + ", " + ans[1]);
  }
}
2, 2

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (ചതുരശ്ര (N)), ഇവിടെ N എന്നത് ഉപയോക്താവിന് നൽകിയ ഏരിയയാണ്. തന്നിരിക്കുന്ന ഏരിയയുടെ എല്ലാ ഹരണങ്ങളും അതിന്റെ സ്‌ക്വയർ റൂട്ട് വരെ കണ്ടെത്താൻ ഞങ്ങൾ ശ്രമിച്ചതിനാൽ, സമയ സങ്കീർണ്ണത ഇൻപുട്ടിന്റെ സ്‌ക്വയർ റൂട്ട് ആണ്.

ബഹിരാകാശ സങ്കീർണ്ണത

O (1), ഞങ്ങൾ സ്ഥിരമായ വേരിയബിളുകൾ മാത്രമേ ഉപയോഗിച്ചിട്ടുള്ളൂ. സ്ഥല സങ്കീർണ്ണതയും സ്ഥിരമാണ്.